1 //===--- DumpAST.cpp - Serialize clang AST to LSP -------------------------===//
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 "DumpAST.h"
10 #include "Protocol.h"
11 #include "SourceCode.h"
12 #include "support/Logger.h"
13 #include "clang/AST/ASTTypeTraits.h"
14 #include "clang/AST/Expr.h"
15 #include "clang/AST/ExprCXX.h"
16 #include "clang/AST/ExternalASTSource.h"
17 #include "clang/AST/NestedNameSpecifier.h"
18 #include "clang/AST/PrettyPrinter.h"
19 #include "clang/AST/RecursiveASTVisitor.h"
20 #include "clang/AST/TextNodeDumper.h"
21 #include "clang/AST/Type.h"
22 #include "clang/AST/TypeLoc.h"
23 #include "clang/Basic/Specifiers.h"
24 #include "clang/Tooling/Syntax/Tokens.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/Support/raw_ostream.h"
27 
28 namespace clang {
29 namespace clangd {
30 namespace {
31 
32 using llvm::raw_ostream;
33 template <typename Print> std::string toString(const Print &C) {
34   std::string Result;
35   llvm::raw_string_ostream OS(Result);
36   C(OS);
37   return std::move(OS.str());
38 }
39 
40 bool isInjectedClassName(Decl *D) {
41   if (const auto *CRD = llvm::dyn_cast<CXXRecordDecl>(D))
42     return CRD->isInjectedClassName();
43   return false;
44 }
45 
46 class DumpVisitor : public RecursiveASTVisitor<DumpVisitor> {
47   using Base = RecursiveASTVisitor<DumpVisitor>;
48 
49   const syntax::TokenBuffer &Tokens;
50   const ASTContext &Ctx;
51 
52   // Pointers are into 'children' vector.
53   // They remain valid because while a node is on the stack we only add
54   // descendants, not siblings.
55   std::vector<ASTNode *> Stack;
56 
57   // Generic logic used to handle traversal of all node kinds.
58 
59   template <typename T>
60   bool traverseNodePre(llvm::StringRef Role, const T &Node) {
61     if (Stack.empty()) {
62       assert(Root.role.empty());
63       Stack.push_back(&Root);
64     } else {
65       Stack.back()->children.emplace_back();
66       Stack.push_back(&Stack.back()->children.back());
67     }
68     auto &N = *Stack.back();
69     N.role = Role.str();
70     N.kind = getKind(Node);
71     N.detail = getDetail(Node);
72     N.range = getRange(Node);
73     N.arcana = getArcana(Node);
74     return true;
75   }
76   bool traverseNodePost() {
77     assert(!Stack.empty());
78     Stack.pop_back();
79     return true;
80   }
81   template <typename T, typename Callable>
82   bool traverseNode(llvm::StringRef Role, const T &Node, const Callable &Body) {
83     traverseNodePre(Role, Node);
84     Body();
85     return traverseNodePost();
86   }
87 
88   // Range: most nodes have getSourceRange(), with a couple of exceptions.
89   // We only return it if it's valid at both ends and there are no macros.
90 
91   template <typename T> llvm::Optional<Range> getRange(const T &Node) {
92     SourceRange SR = getSourceRange(Node);
93     auto Spelled = Tokens.spelledForExpanded(Tokens.expandedTokens(SR));
94     if (!Spelled)
95       return llvm::None;
96     return halfOpenToRange(
97         Tokens.sourceManager(),
98         CharSourceRange::getCharRange(Spelled->front().location(),
99                                       Spelled->back().endLocation()));
100   }
101   template <typename T, typename = decltype(std::declval<T>().getSourceRange())>
102   SourceRange getSourceRange(const T &Node) {
103     return Node.getSourceRange();
104   }
105   template <typename T,
106             typename = decltype(std::declval<T *>()->getSourceRange())>
107   SourceRange getSourceRange(const T *Node) {
108     return Node->getSourceRange();
109   }
110   // TemplateName doesn't have a real Loc node type.
111   SourceRange getSourceRange(const TemplateName &Node) { return SourceRange(); }
112   // Attr just uses a weird method name. Maybe we should fix it instead?
113   SourceRange getSourceRange(const Attr *Node) { return Node->getRange(); }
114 
115   // Kind is usualy the class name, without the suffix ("Type" etc).
116   // Where there's a set of variants instead, we use the 'Kind' enum values.
117 
118   std::string getKind(const Decl *D) { return D->getDeclKindName(); }
119   std::string getKind(const Stmt *S) {
120     std::string Result = S->getStmtClassName();
121     if (llvm::StringRef(Result).endswith("Stmt") ||
122         llvm::StringRef(Result).endswith("Expr"))
123       Result.resize(Result.size() - 4);
124     return Result;
125   }
126   std::string getKind(const TypeLoc &TL) {
127     std::string Result;
128     if (TL.getTypeLocClass() == TypeLoc::Qualified)
129       return "Qualified";
130     return TL.getType()->getTypeClassName();
131   }
132   std::string getKind(const TemplateArgumentLoc &TAL) {
133     switch (TAL.getArgument().getKind()) {
134 #define TEMPLATE_ARGUMENT_KIND(X)                                              \
135   case TemplateArgument::X:                                                    \
136     return #X
137       TEMPLATE_ARGUMENT_KIND(Null);
138       TEMPLATE_ARGUMENT_KIND(NullPtr);
139       TEMPLATE_ARGUMENT_KIND(Expression);
140       TEMPLATE_ARGUMENT_KIND(Integral);
141       TEMPLATE_ARGUMENT_KIND(Pack);
142       TEMPLATE_ARGUMENT_KIND(Type);
143       TEMPLATE_ARGUMENT_KIND(Declaration);
144       TEMPLATE_ARGUMENT_KIND(Template);
145       TEMPLATE_ARGUMENT_KIND(TemplateExpansion);
146 #undef TEMPLATE_ARGUMENT_KIND
147     }
148     llvm_unreachable("Unhandled ArgKind enum");
149   }
150   std::string getKind(const NestedNameSpecifierLoc &NNSL) {
151     assert(NNSL.getNestedNameSpecifier());
152     switch (NNSL.getNestedNameSpecifier()->getKind()) {
153 #define NNS_KIND(X)                                                            \
154   case NestedNameSpecifier::X:                                                 \
155     return #X
156       NNS_KIND(Identifier);
157       NNS_KIND(Namespace);
158       NNS_KIND(TypeSpec);
159       NNS_KIND(TypeSpecWithTemplate);
160       NNS_KIND(Global);
161       NNS_KIND(Super);
162       NNS_KIND(NamespaceAlias);
163 #undef NNS_KIND
164     }
165     llvm_unreachable("Unhandled SpecifierKind enum");
166   }
167   std::string getKind(const CXXCtorInitializer *CCI) {
168     if (CCI->isBaseInitializer())
169       return "BaseInitializer";
170     if (CCI->isDelegatingInitializer())
171       return "DelegatingInitializer";
172     if (CCI->isAnyMemberInitializer())
173       return "MemberInitializer";
174     llvm_unreachable("Unhandled CXXCtorInitializer type");
175   }
176   std::string getKind(const TemplateName &TN) {
177     switch (TN.getKind()) {
178 #define TEMPLATE_KIND(X)                                                       \
179   case TemplateName::X:                                                        \
180     return #X;
181       TEMPLATE_KIND(Template);
182       TEMPLATE_KIND(OverloadedTemplate);
183       TEMPLATE_KIND(AssumedTemplate);
184       TEMPLATE_KIND(QualifiedTemplate);
185       TEMPLATE_KIND(DependentTemplate);
186       TEMPLATE_KIND(SubstTemplateTemplateParm);
187       TEMPLATE_KIND(SubstTemplateTemplateParmPack);
188 #undef TEMPLATE_KIND
189     }
190     llvm_unreachable("Unhandled NameKind enum");
191   }
192   std::string getKind(const Attr *A) {
193     switch (A->getKind()) {
194 #define ATTR(X)                                                                \
195   case attr::X:                                                                \
196     return #X;
197 #include "clang/Basic/AttrList.inc"
198 #undef ATTR
199     }
200     llvm_unreachable("Unhandled attr::Kind enum");
201   }
202   std::string getKind(const CXXBaseSpecifier &CBS) {
203     // There aren't really any variants of CXXBaseSpecifier.
204     // To avoid special cases in the API/UI, use public/private as the kind.
205     return getAccessSpelling(CBS.getAccessSpecifier()).str();
206   }
207 
208   // Detail is the single most important fact about the node.
209   // Often this is the name, sometimes a "kind" enum like operators or casts.
210   // We should avoid unbounded text, like dumping parameter lists.
211 
212   std::string getDetail(const Decl *D) {
213     const auto *ND = dyn_cast<NamedDecl>(D);
214     if (!ND || llvm::isa_and_nonnull<CXXConstructorDecl>(ND->getAsFunction()) ||
215         isa<CXXDestructorDecl>(ND))
216       return "";
217     std::string Name = toString([&](raw_ostream &OS) { ND->printName(OS); });
218     if (Name.empty())
219       return "(anonymous)";
220     return Name;
221   }
222   std::string getDetail(const Stmt *S) {
223     if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
224       return DRE->getNameInfo().getAsString();
225     if (const auto *DSDRE = dyn_cast<DependentScopeDeclRefExpr>(S))
226       return DSDRE->getNameInfo().getAsString();
227     if (const auto *ME = dyn_cast<MemberExpr>(S))
228       return ME->getMemberNameInfo().getAsString();
229     if (const auto *CE = dyn_cast<CastExpr>(S))
230       return CE->getCastKindName();
231     if (const auto *BO = dyn_cast<BinaryOperator>(S))
232       return BO->getOpcodeStr().str();
233     if (const auto *UO = dyn_cast<UnaryOperator>(S))
234       return UnaryOperator::getOpcodeStr(UO->getOpcode()).str();
235     if (const auto *CCO = dyn_cast<CXXConstructExpr>(S))
236       return CCO->getConstructor()->getNameAsString();
237     if (const auto *CTE = dyn_cast<CXXThisExpr>(S)) {
238       bool Const = CTE->getType()->getPointeeType().isLocalConstQualified();
239       if (CTE->isImplicit())
240         return Const ? "const, implicit" : "implicit";
241       if (Const)
242         return "const";
243       return "";
244     }
245     if (isa<IntegerLiteral, FloatingLiteral, FixedPointLiteral,
246             CharacterLiteral, ImaginaryLiteral, CXXBoolLiteralExpr>(S))
247       return toString([&](raw_ostream &OS) {
248         S->printPretty(OS, nullptr, Ctx.getPrintingPolicy());
249       });
250     if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(S))
251       return MTE->isBoundToLvalueReference() ? "lvalue" : "rvalue";
252     return "";
253   }
254   std::string getDetail(const TypeLoc &TL) {
255     if (TL.getType().hasLocalQualifiers())
256       return TL.getType().getLocalQualifiers().getAsString(
257           Ctx.getPrintingPolicy());
258     if (const auto *TT = dyn_cast<TagType>(TL.getTypePtr()))
259       return getDetail(TT->getDecl());
260     if (const auto *DT = dyn_cast<DeducedType>(TL.getTypePtr()))
261       if (DT->isDeduced())
262         return DT->getDeducedType().getAsString(Ctx.getPrintingPolicy());
263     if (const auto *BT = dyn_cast<BuiltinType>(TL.getTypePtr()))
264       return BT->getName(Ctx.getPrintingPolicy()).str();
265     if (const auto *TTPT = dyn_cast<TemplateTypeParmType>(TL.getTypePtr()))
266       return getDetail(TTPT->getDecl());
267     if (const auto *TT = dyn_cast<TypedefType>(TL.getTypePtr()))
268       return getDetail(TT->getDecl());
269     return "";
270   }
271   std::string getDetail(const NestedNameSpecifierLoc &NNSL) {
272     const auto &NNS = *NNSL.getNestedNameSpecifier();
273     switch (NNS.getKind()) {
274     case NestedNameSpecifier::Identifier:
275       return NNS.getAsIdentifier()->getName().str() + "::";
276     case NestedNameSpecifier::Namespace:
277       return NNS.getAsNamespace()->getNameAsString() + "::";
278     case NestedNameSpecifier::NamespaceAlias:
279       return NNS.getAsNamespaceAlias()->getNameAsString() + "::";
280     default:
281       return "";
282     }
283   }
284   std::string getDetail(const CXXCtorInitializer *CCI) {
285     if (FieldDecl *FD = CCI->getAnyMember())
286       return getDetail(FD);
287     if (TypeLoc TL = CCI->getBaseClassLoc())
288       return getDetail(TL);
289     return "";
290   }
291   std::string getDetail(const TemplateArgumentLoc &TAL) {
292     if (TAL.getArgument().getKind() == TemplateArgument::Integral)
293       return TAL.getArgument().getAsIntegral().toString(10);
294     return "";
295   }
296   std::string getDetail(const TemplateName &TN) {
297     return toString([&](raw_ostream &OS) {
298       TN.print(OS, Ctx.getPrintingPolicy(), /*SuppressNNS=*/true);
299     });
300   }
301   std::string getDetail(const Attr *A) {
302     return A->getAttrName() ? A->getNormalizedFullName() : A->getSpelling();
303   }
304   std::string getDetail(const CXXBaseSpecifier &CBS) {
305     return CBS.isVirtual() ? "virtual" : "";
306   }
307 
308   /// Arcana is produced by TextNodeDumper, for the types it supports.
309 
310   template <typename Dump> std::string dump(const Dump &D) {
311     return toString([&](raw_ostream &OS) {
312       TextNodeDumper Dumper(OS, Ctx, /*ShowColors=*/false);
313       D(Dumper);
314     });
315   }
316   template <typename T> std::string getArcana(const T &N) {
317     return dump([&](TextNodeDumper &D) { D.Visit(N); });
318   }
319   std::string getArcana(const NestedNameSpecifierLoc &NNS) { return ""; }
320   std::string getArcana(const TemplateName &NNS) { return ""; }
321   std::string getArcana(const CXXBaseSpecifier &CBS) { return ""; }
322   std::string getArcana(const TemplateArgumentLoc &TAL) {
323     return dump([&](TextNodeDumper &D) {
324       D.Visit(TAL.getArgument(), TAL.getSourceRange());
325     });
326   }
327   std::string getArcana(const TypeLoc &TL) {
328     return dump([&](TextNodeDumper &D) { D.Visit(TL.getType()); });
329   }
330 
331 public:
332   ASTNode Root;
333   DumpVisitor(const syntax::TokenBuffer &Tokens, const ASTContext &Ctx)
334       : Tokens(Tokens), Ctx(Ctx) {}
335 
336   // Override traversal to record the nodes we care about.
337   // Generally, these are nodes with position information (TypeLoc, not Type).
338 
339   bool TraverseDecl(Decl *D) {
340     return !D || isInjectedClassName(D) || traverseNode("declaration", D, [&] {
341       if (isa<TranslationUnitDecl>(D))
342         Base::TraverseAST(const_cast<ASTContext &>(Ctx));
343       else
344         Base::TraverseDecl(D);
345     });
346   }
347   bool TraverseTypeLoc(TypeLoc TL) {
348     return !TL || traverseNode("type", TL, [&] { Base::TraverseTypeLoc(TL); });
349   }
350   bool TraverseTemplateName(const TemplateName &TN) {
351     return traverseNode("template name", TN,
352                         [&] { Base::TraverseTemplateName(TN); });
353   }
354   bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &TAL) {
355     return traverseNode("template argument", TAL,
356                         [&] { Base::TraverseTemplateArgumentLoc(TAL); });
357   }
358   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSL) {
359     return !NNSL || traverseNode("specifier", NNSL, [&] {
360       Base::TraverseNestedNameSpecifierLoc(NNSL);
361     });
362   }
363   bool TraverseConstructorInitializer(CXXCtorInitializer *CCI) {
364     return !CCI || traverseNode("constructor initializer", CCI, [&] {
365       Base::TraverseConstructorInitializer(CCI);
366     });
367   }
368   bool TraverseAttr(Attr *A) {
369     return !A || traverseNode("attribute", A, [&] { Base::TraverseAttr(A); });
370   }
371   bool TraverseCXXBaseSpecifier(const CXXBaseSpecifier &CBS) {
372     return traverseNode("base", CBS,
373                         [&] { Base::TraverseCXXBaseSpecifier(CBS); });
374   }
375   // Stmt is the same, but this form allows the data recursion optimization.
376   bool dataTraverseStmtPre(Stmt *S) {
377     return S && traverseNodePre(isa<Expr>(S) ? "expression" : "statement", S);
378   }
379   bool dataTraverseStmtPost(Stmt *X) { return traverseNodePost(); }
380 
381   // QualifiedTypeLoc is handled strangely in RecursiveASTVisitor: the derived
382   // TraverseTypeLoc is not called for the inner UnqualTypeLoc.
383   // This means we'd never see 'int' in 'const int'! Work around that here.
384   // (The reason for the behavior is to avoid traversing the nested Type twice,
385   // but we ignore TraverseType anyway).
386   bool TraverseQualifiedTypeLoc(QualifiedTypeLoc QTL) {
387     return TraverseTypeLoc(QTL.getUnqualifiedLoc());
388   }
389   // Uninteresting parts of the AST that don't have locations within them.
390   bool TraverseNestedNameSpecifier(NestedNameSpecifier *) { return true; }
391   bool TraverseType(QualType) { return true; }
392 
393   // OpaqueValueExpr blocks traversal, we must explicitly traverse it.
394   bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
395     return TraverseStmt(E->getSourceExpr());
396   }
397   // We only want to traverse the *syntactic form* to understand the selection.
398   bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
399     return TraverseStmt(E->getSyntacticForm());
400   }
401 };
402 
403 } // namespace
404 
405 ASTNode dumpAST(const DynTypedNode &N, const syntax::TokenBuffer &Tokens,
406                 const ASTContext &Ctx) {
407   DumpVisitor V(Tokens, Ctx);
408   // DynTypedNode only works with const, RecursiveASTVisitor only non-const :-(
409   if (const auto *D = N.get<Decl>())
410     V.TraverseDecl(const_cast<Decl *>(D));
411   else if (const auto *S = N.get<Stmt>())
412     V.TraverseStmt(const_cast<Stmt *>(S));
413   else if (const auto *NNSL = N.get<NestedNameSpecifierLoc>())
414     V.TraverseNestedNameSpecifierLoc(
415         *const_cast<NestedNameSpecifierLoc *>(NNSL));
416   else if (const auto *NNS = N.get<NestedNameSpecifier>())
417     V.TraverseNestedNameSpecifier(const_cast<NestedNameSpecifier *>(NNS));
418   else if (const auto *TL = N.get<TypeLoc>())
419     V.TraverseTypeLoc(*const_cast<TypeLoc *>(TL));
420   else if (const auto *QT = N.get<QualType>())
421     V.TraverseType(*const_cast<QualType *>(QT));
422   else if (const auto *CCI = N.get<CXXCtorInitializer>())
423     V.TraverseConstructorInitializer(const_cast<CXXCtorInitializer *>(CCI));
424   else if (const auto *TAL = N.get<TemplateArgumentLoc>())
425     V.TraverseTemplateArgumentLoc(*const_cast<TemplateArgumentLoc *>(TAL));
426   else if (const auto *CBS = N.get<CXXBaseSpecifier>())
427     V.TraverseCXXBaseSpecifier(*const_cast<CXXBaseSpecifier *>(CBS));
428   else
429     elog("dumpAST: unhandled DynTypedNode kind {0}",
430          N.getNodeKind().asStringRef());
431   return std::move(V.Root);
432 }
433 
434 } // namespace clangd
435 } // namespace clang
436