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;
toString(const Print & C)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
isInjectedClassName(Decl * D)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>
traverseNodePre(llvm::StringRef Role,const T & Node)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 }
traverseNodePost()76 bool traverseNodePost() {
77 assert(!Stack.empty());
78 Stack.pop_back();
79 return true;
80 }
81 template <typename T, typename Callable>
traverseNode(llvm::StringRef Role,const T & Node,const Callable & Body)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
getRange(const T & Node)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())>
getSourceRange(const T & Node)102 SourceRange getSourceRange(const T &Node) {
103 return Node.getSourceRange();
104 }
105 template <typename T,
106 typename = decltype(std::declval<T *>()->getSourceRange())>
getSourceRange(const T * Node)107 SourceRange getSourceRange(const T *Node) {
108 return Node->getSourceRange();
109 }
110 // TemplateName doesn't have a real Loc node type.
getSourceRange(const TemplateName & Node)111 SourceRange getSourceRange(const TemplateName &Node) { return SourceRange(); }
112 // Attr just uses a weird method name. Maybe we should fix it instead?
getSourceRange(const Attr * Node)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
getKind(const Decl * D)118 std::string getKind(const Decl *D) { return D->getDeclKindName(); }
getKind(const Stmt * S)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 }
getKind(const TypeLoc & TL)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 }
getKind(const TemplateArgumentLoc & TAL)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 }
getKind(const NestedNameSpecifierLoc & NNSL)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 }
getKind(const CXXCtorInitializer * CCI)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 }
getKind(const TemplateName & TN)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 }
getKind(const Attr * A)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 }
getKind(const CXXBaseSpecifier & CBS)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
getDetail(const Decl * D)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 }
getDetail(const Stmt * S)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 }
getDetail(const TypeLoc & TL)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 }
getDetail(const NestedNameSpecifierLoc & NNSL)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 }
getDetail(const CXXCtorInitializer * CCI)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 }
getDetail(const TemplateArgumentLoc & TAL)291 std::string getDetail(const TemplateArgumentLoc &TAL) {
292 if (TAL.getArgument().getKind() == TemplateArgument::Integral)
293 return TAL.getArgument().getAsIntegral().toString(10);
294 return "";
295 }
getDetail(const TemplateName & TN)296 std::string getDetail(const TemplateName &TN) {
297 return toString([&](raw_ostream &OS) {
298 TN.print(OS, Ctx.getPrintingPolicy(), /*SuppressNNS=*/true);
299 });
300 }
getDetail(const Attr * A)301 std::string getDetail(const Attr *A) {
302 return A->getAttrName() ? A->getNormalizedFullName() : A->getSpelling();
303 }
getDetail(const CXXBaseSpecifier & CBS)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
dump(const Dump & D)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 }
getArcana(const T & N)316 template <typename T> std::string getArcana(const T &N) {
317 return dump([&](TextNodeDumper &D) { D.Visit(N); });
318 }
getArcana(const NestedNameSpecifierLoc & NNS)319 std::string getArcana(const NestedNameSpecifierLoc &NNS) { return ""; }
getArcana(const TemplateName & NNS)320 std::string getArcana(const TemplateName &NNS) { return ""; }
getArcana(const CXXBaseSpecifier & CBS)321 std::string getArcana(const CXXBaseSpecifier &CBS) { return ""; }
getArcana(const TemplateArgumentLoc & TAL)322 std::string getArcana(const TemplateArgumentLoc &TAL) {
323 return dump([&](TextNodeDumper &D) {
324 D.Visit(TAL.getArgument(), TAL.getSourceRange());
325 });
326 }
getArcana(const TypeLoc & TL)327 std::string getArcana(const TypeLoc &TL) {
328 return dump([&](TextNodeDumper &D) { D.Visit(TL.getType()); });
329 }
330
331 public:
332 ASTNode Root;
DumpVisitor(const syntax::TokenBuffer & Tokens,const ASTContext & Ctx)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).
TraverseDecl(Decl * D)338 bool TraverseDecl(Decl *D) {
339 return !D || isInjectedClassName(D) ||
340 traverseNode("declaration", D, [&] { Base::TraverseDecl(D); });
341 }
TraverseTypeLoc(TypeLoc TL)342 bool TraverseTypeLoc(TypeLoc TL) {
343 return !TL || traverseNode("type", TL, [&] { Base::TraverseTypeLoc(TL); });
344 }
TraverseTemplateName(const TemplateName & TN)345 bool TraverseTemplateName(const TemplateName &TN) {
346 return traverseNode("template name", TN,
347 [&] { Base::TraverseTemplateName(TN); });
348 }
TraverseTemplateArgumentLoc(const TemplateArgumentLoc & TAL)349 bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &TAL) {
350 return traverseNode("template argument", TAL,
351 [&] { Base::TraverseTemplateArgumentLoc(TAL); });
352 }
TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSL)353 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSL) {
354 return !NNSL || traverseNode("specifier", NNSL, [&] {
355 Base::TraverseNestedNameSpecifierLoc(NNSL);
356 });
357 }
TraverseConstructorInitializer(CXXCtorInitializer * CCI)358 bool TraverseConstructorInitializer(CXXCtorInitializer *CCI) {
359 return !CCI || traverseNode("constructor initializer", CCI, [&] {
360 Base::TraverseConstructorInitializer(CCI);
361 });
362 }
TraverseAttr(Attr * A)363 bool TraverseAttr(Attr *A) {
364 return !A || traverseNode("attribute", A, [&] { Base::TraverseAttr(A); });
365 }
TraverseCXXBaseSpecifier(const CXXBaseSpecifier & CBS)366 bool TraverseCXXBaseSpecifier(const CXXBaseSpecifier &CBS) {
367 return traverseNode("base", CBS,
368 [&] { Base::TraverseCXXBaseSpecifier(CBS); });
369 }
370 // Stmt is the same, but this form allows the data recursion optimization.
dataTraverseStmtPre(Stmt * S)371 bool dataTraverseStmtPre(Stmt *S) {
372 return S && traverseNodePre(isa<Expr>(S) ? "expression" : "statement", S);
373 }
dataTraverseStmtPost(Stmt * X)374 bool dataTraverseStmtPost(Stmt *X) { return traverseNodePost(); }
375
376 // QualifiedTypeLoc is handled strangely in RecursiveASTVisitor: the derived
377 // TraverseTypeLoc is not called for the inner UnqualTypeLoc.
378 // This means we'd never see 'int' in 'const int'! Work around that here.
379 // (The reason for the behavior is to avoid traversing the nested Type twice,
380 // but we ignore TraverseType anyway).
TraverseQualifiedTypeLoc(QualifiedTypeLoc QTL)381 bool TraverseQualifiedTypeLoc(QualifiedTypeLoc QTL) {
382 return TraverseTypeLoc(QTL.getUnqualifiedLoc());
383 }
384 // Uninteresting parts of the AST that don't have locations within them.
TraverseNestedNameSpecifier(NestedNameSpecifier *)385 bool TraverseNestedNameSpecifier(NestedNameSpecifier *) { return true; }
TraverseType(QualType)386 bool TraverseType(QualType) { return true; }
387
388 // OpaqueValueExpr blocks traversal, we must explicitly traverse it.
TraverseOpaqueValueExpr(OpaqueValueExpr * E)389 bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
390 return TraverseStmt(E->getSourceExpr());
391 }
392 // We only want to traverse the *syntactic form* to understand the selection.
TraversePseudoObjectExpr(PseudoObjectExpr * E)393 bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
394 return TraverseStmt(E->getSyntacticForm());
395 }
396 };
397
398 } // namespace
399
dumpAST(const DynTypedNode & N,const syntax::TokenBuffer & Tokens,const ASTContext & Ctx)400 ASTNode dumpAST(const DynTypedNode &N, const syntax::TokenBuffer &Tokens,
401 const ASTContext &Ctx) {
402 DumpVisitor V(Tokens, Ctx);
403 // DynTypedNode only works with const, RecursiveASTVisitor only non-const :-(
404 if (const auto *D = N.get<Decl>())
405 V.TraverseDecl(const_cast<Decl *>(D));
406 else if (const auto *S = N.get<Stmt>())
407 V.TraverseStmt(const_cast<Stmt *>(S));
408 else if (const auto *NNSL = N.get<NestedNameSpecifierLoc>())
409 V.TraverseNestedNameSpecifierLoc(
410 *const_cast<NestedNameSpecifierLoc *>(NNSL));
411 else if (const auto *NNS = N.get<NestedNameSpecifier>())
412 V.TraverseNestedNameSpecifier(const_cast<NestedNameSpecifier *>(NNS));
413 else if (const auto *TL = N.get<TypeLoc>())
414 V.TraverseTypeLoc(*const_cast<TypeLoc *>(TL));
415 else if (const auto *QT = N.get<QualType>())
416 V.TraverseType(*const_cast<QualType *>(QT));
417 else if (const auto *CCI = N.get<CXXCtorInitializer>())
418 V.TraverseConstructorInitializer(const_cast<CXXCtorInitializer *>(CCI));
419 else if (const auto *TAL = N.get<TemplateArgumentLoc>())
420 V.TraverseTemplateArgumentLoc(*const_cast<TemplateArgumentLoc *>(TAL));
421 else if (const auto *CBS = N.get<CXXBaseSpecifier>())
422 V.TraverseCXXBaseSpecifier(*const_cast<CXXBaseSpecifier *>(CBS));
423 else
424 elog("dumpAST: unhandled DynTypedNode kind {0}",
425 N.getNodeKind().asStringRef());
426 return std::move(V.Root);
427 }
428
429 } // namespace clangd
430 } // namespace clang
431