llvm-project

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/NestedNameSpecifier.h"
17
#include "clang/AST/PrettyPrinter.h"
18
#include "clang/AST/RecursiveASTVisitor.h"
19
#include "clang/AST/TextNodeDumper.h"
20
#include "clang/AST/Type.h"
21
#include "clang/AST/TypeLoc.h"
22
#include "clang/Basic/Specifiers.h"
23
#include "clang/Tooling/Syntax/Tokens.h"
24
#include "llvm/ADT/StringRef.h"
25
#include "llvm/Support/raw_ostream.h"
26
#include <optional>
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> std::optional<Range> getRange(const T &Node) {
92
    SourceRange SR = getSourceRange(Node);
93
    auto Spelled = Tokens.spelledForExpanded(Tokens.expandedTokens(SR));
94
    if (!Spelled)
95
      return std::nullopt;
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 usually 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).ends_with("Stmt") ||
122
        llvm::StringRef(Result).ends_with("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
      TEMPLATE_ARGUMENT_KIND(StructuralValue);
147
#undef TEMPLATE_ARGUMENT_KIND
148
    }
149
    llvm_unreachable("Unhandled ArgKind enum");
150
  }
151
  std::string getKind(const NestedNameSpecifierLoc &NNSL) {
152
    assert(NNSL.getNestedNameSpecifier());
153
    switch (NNSL.getNestedNameSpecifier()->getKind()) {
154
#define NNS_KIND(X)                                                            \
155
  case NestedNameSpecifier::X:                                                 \
156
    return #X
157
      NNS_KIND(Identifier);
158
      NNS_KIND(Namespace);
159
      NNS_KIND(TypeSpec);
160
      NNS_KIND(TypeSpecWithTemplate);
161
      NNS_KIND(Global);
162
      NNS_KIND(Super);
163
      NNS_KIND(NamespaceAlias);
164
#undef NNS_KIND
165
    }
166
    llvm_unreachable("Unhandled SpecifierKind enum");
167
  }
168
  std::string getKind(const CXXCtorInitializer *CCI) {
169
    if (CCI->isBaseInitializer())
170
      return "BaseInitializer";
171
    if (CCI->isDelegatingInitializer())
172
      return "DelegatingInitializer";
173
    if (CCI->isAnyMemberInitializer())
174
      return "MemberInitializer";
175
    llvm_unreachable("Unhandled CXXCtorInitializer type");
176
  }
177
  std::string getKind(const TemplateName &TN) {
178
    switch (TN.getKind()) {
179
#define TEMPLATE_KIND(X)                                                       \
180
  case TemplateName::X:                                                        \
181
    return #X;
182
      TEMPLATE_KIND(Template);
183
      TEMPLATE_KIND(OverloadedTemplate);
184
      TEMPLATE_KIND(AssumedTemplate);
185
      TEMPLATE_KIND(QualifiedTemplate);
186
      TEMPLATE_KIND(DependentTemplate);
187
      TEMPLATE_KIND(SubstTemplateTemplateParm);
188
      TEMPLATE_KIND(SubstTemplateTemplateParmPack);
189
      TEMPLATE_KIND(UsingTemplate);
190
#undef TEMPLATE_KIND
191
    }
192
    llvm_unreachable("Unhandled NameKind enum");
193
  }
194
  std::string getKind(const Attr *A) {
195
    switch (A->getKind()) {
196
#define ATTR(X)                                                                \
197
  case attr::X:                                                                \
198
    return #X;
199
#include "clang/Basic/AttrList.inc"
200
#undef ATTR
201
    }
202
    llvm_unreachable("Unhandled attr::Kind enum");
203
  }
204
  std::string getKind(const CXXBaseSpecifier &CBS) {
205
    // There aren't really any variants of CXXBaseSpecifier.
206
    // To avoid special cases in the API/UI, use public/private as the kind.
207
    return getAccessSpelling(CBS.getAccessSpecifier()).str();
208
  }
209
  std::string getKind(const ConceptReference *CR) {
210
    // Again there are no variants here.
211
    // Kind is "Concept", role is "reference"
212
    return "Concept";
213
  }
214

215
  // Detail is the single most important fact about the node.
216
  // Often this is the name, sometimes a "kind" enum like operators or casts.
217
  // We should avoid unbounded text, like dumping parameter lists.
218

219
  std::string getDetail(const Decl *D) {
220
    const auto *ND = dyn_cast<NamedDecl>(D);
221
    if (!ND || llvm::isa_and_nonnull<CXXConstructorDecl>(ND->getAsFunction()) ||
222
        isa<CXXDestructorDecl>(ND))
223
      return "";
224
    std::string Name = toString([&](raw_ostream &OS) { ND->printName(OS); });
225
    if (Name.empty())
226
      return "(anonymous)";
227
    return Name;
228
  }
229
  std::string getDetail(const Stmt *S) {
230
    if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
231
      return DRE->getNameInfo().getAsString();
232
    if (const auto *DSDRE = dyn_cast<DependentScopeDeclRefExpr>(S))
233
      return DSDRE->getNameInfo().getAsString();
234
    if (const auto *ME = dyn_cast<MemberExpr>(S))
235
      return ME->getMemberNameInfo().getAsString();
236
    if (const auto *CE = dyn_cast<CastExpr>(S))
237
      return CE->getCastKindName();
238
    if (const auto *BO = dyn_cast<BinaryOperator>(S))
239
      return BO->getOpcodeStr().str();
240
    if (const auto *UO = dyn_cast<UnaryOperator>(S))
241
      return UnaryOperator::getOpcodeStr(UO->getOpcode()).str();
242
    if (const auto *CCO = dyn_cast<CXXConstructExpr>(S))
243
      return CCO->getConstructor()->getNameAsString();
244
    if (const auto *CTE = dyn_cast<CXXThisExpr>(S)) {
245
      bool Const = CTE->getType()->getPointeeType().isLocalConstQualified();
246
      if (CTE->isImplicit())
247
        return Const ? "const, implicit" : "implicit";
248
      if (Const)
249
        return "const";
250
      return "";
251
    }
252
    if (isa<IntegerLiteral, FloatingLiteral, FixedPointLiteral,
253
            CharacterLiteral, ImaginaryLiteral, CXXBoolLiteralExpr>(S))
254
      return toString([&](raw_ostream &OS) {
255
        S->printPretty(OS, nullptr, Ctx.getPrintingPolicy());
256
      });
257
    if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(S))
258
      return MTE->isBoundToLvalueReference() ? "lvalue" : "rvalue";
259
    return "";
260
  }
261
  std::string getDetail(const TypeLoc &TL) {
262
    if (TL.getType().hasLocalQualifiers())
263
      return TL.getType().getLocalQualifiers().getAsString(
264
          Ctx.getPrintingPolicy());
265
    if (const auto *TT = dyn_cast<TagType>(TL.getTypePtr()))
266
      return getDetail(TT->getDecl());
267
    if (const auto *DT = dyn_cast<DeducedType>(TL.getTypePtr()))
268
      if (DT->isDeduced())
269
        return DT->getDeducedType().getAsString(Ctx.getPrintingPolicy());
270
    if (const auto *BT = dyn_cast<BuiltinType>(TL.getTypePtr()))
271
      return BT->getName(Ctx.getPrintingPolicy()).str();
272
    if (const auto *TTPT = dyn_cast<TemplateTypeParmType>(TL.getTypePtr()))
273
      return getDetail(TTPT->getDecl());
274
    if (const auto *TT = dyn_cast<TypedefType>(TL.getTypePtr()))
275
      return getDetail(TT->getDecl());
276
    return "";
277
  }
278
  std::string getDetail(const NestedNameSpecifierLoc &NNSL) {
279
    const auto &NNS = *NNSL.getNestedNameSpecifier();
280
    switch (NNS.getKind()) {
281
    case NestedNameSpecifier::Identifier:
282
      return NNS.getAsIdentifier()->getName().str() + "::";
283
    case NestedNameSpecifier::Namespace:
284
      return NNS.getAsNamespace()->getNameAsString() + "::";
285
    case NestedNameSpecifier::NamespaceAlias:
286
      return NNS.getAsNamespaceAlias()->getNameAsString() + "::";
287
    default:
288
      return "";
289
    }
290
  }
291
  std::string getDetail(const CXXCtorInitializer *CCI) {
292
    if (FieldDecl *FD = CCI->getAnyMember())
293
      return getDetail(FD);
294
    if (TypeLoc TL = CCI->getBaseClassLoc())
295
      return getDetail(TL);
296
    return "";
297
  }
298
  std::string getDetail(const TemplateArgumentLoc &TAL) {
299
    if (TAL.getArgument().getKind() == TemplateArgument::Integral)
300
      return toString(TAL.getArgument().getAsIntegral(), 10);
301
    return "";
302
  }
303
  std::string getDetail(const TemplateName &TN) {
304
    return toString([&](raw_ostream &OS) {
305
      TN.print(OS, Ctx.getPrintingPolicy(), TemplateName::Qualified::None);
306
    });
307
  }
308
  std::string getDetail(const Attr *A) {
309
    return A->getAttrName() ? A->getNormalizedFullName() : A->getSpelling();
310
  }
311
  std::string getDetail(const CXXBaseSpecifier &CBS) {
312
    return CBS.isVirtual() ? "virtual" : "";
313
  }
314
  std::string getDetail(const ConceptReference *CR) {
315
    return CR->getNamedConcept()->getNameAsString();
316
  }
317

318
  /// Arcana is produced by TextNodeDumper, for the types it supports.
319

320
  template <typename Dump> std::string dump(const Dump &D) {
321
    return toString([&](raw_ostream &OS) {
322
      TextNodeDumper Dumper(OS, Ctx, /*ShowColors=*/false);
323
      D(Dumper);
324
    });
325
  }
326
  template <typename T> std::string getArcana(const T &N) {
327
    return dump([&](TextNodeDumper &D) { D.Visit(N); });
328
  }
329
  std::string getArcana(const NestedNameSpecifierLoc &NNS) { return ""; }
330
  std::string getArcana(const TemplateName &NNS) { return ""; }
331
  std::string getArcana(const CXXBaseSpecifier &CBS) { return ""; }
332
  std::string getArcana(const TemplateArgumentLoc &TAL) {
333
    return dump([&](TextNodeDumper &D) {
334
      D.Visit(TAL.getArgument(), TAL.getSourceRange());
335
    });
336
  }
337
  std::string getArcana(const TypeLoc &TL) {
338
    return dump([&](TextNodeDumper &D) { D.Visit(TL.getType()); });
339
  }
340

341
public:
342
  ASTNode Root;
343
  DumpVisitor(const syntax::TokenBuffer &Tokens, const ASTContext &Ctx)
344
      : Tokens(Tokens), Ctx(Ctx) {}
345

346
  // Override traversal to record the nodes we care about.
347
  // Generally, these are nodes with position information (TypeLoc, not Type).
348

349
  bool TraverseDecl(Decl *D) {
350
    return !D || isInjectedClassName(D) ||
351
           traverseNode("declaration", D, [&] { Base::TraverseDecl(D); });
352
  }
353
  bool TraverseTypeLoc(TypeLoc TL) {
354
    return !TL || traverseNode("type", TL, [&] { Base::TraverseTypeLoc(TL); });
355
  }
356
  bool TraverseTemplateName(const TemplateName &TN) {
357
    return traverseNode("template name", TN,
358
                        [&] { Base::TraverseTemplateName(TN); });
359
  }
360
  bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &TAL) {
361
    return traverseNode("template argument", TAL,
362
                        [&] { Base::TraverseTemplateArgumentLoc(TAL); });
363
  }
364
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNSL) {
365
    return !NNSL || traverseNode("specifier", NNSL, [&] {
366
      Base::TraverseNestedNameSpecifierLoc(NNSL);
367
    });
368
  }
369
  bool TraverseConstructorInitializer(CXXCtorInitializer *CCI) {
370
    return !CCI || traverseNode("constructor initializer", CCI, [&] {
371
      Base::TraverseConstructorInitializer(CCI);
372
    });
373
  }
374
  bool TraverseAttr(Attr *A) {
375
    return !A || traverseNode("attribute", A, [&] { Base::TraverseAttr(A); });
376
  }
377
  bool TraverseConceptReference(ConceptReference *C) {
378
    return !C || traverseNode("reference", C,
379
                              [&] { Base::TraverseConceptReference(C); });
380
  }
381
  bool TraverseCXXBaseSpecifier(const CXXBaseSpecifier &CBS) {
382
    return traverseNode("base", CBS,
383
                        [&] { Base::TraverseCXXBaseSpecifier(CBS); });
384
  }
385
  // Stmt is the same, but this form allows the data recursion optimization.
386
  bool dataTraverseStmtPre(Stmt *S) {
387
    return S && traverseNodePre(isa<Expr>(S) ? "expression" : "statement", S);
388
  }
389
  bool dataTraverseStmtPost(Stmt *X) { return traverseNodePost(); }
390

391
  // QualifiedTypeLoc is handled strangely in RecursiveASTVisitor: the derived
392
  // TraverseTypeLoc is not called for the inner UnqualTypeLoc.
393
  // This means we'd never see 'int' in 'const int'! Work around that here.
394
  // (The reason for the behavior is to avoid traversing the nested Type twice,
395
  // but we ignore TraverseType anyway).
396
  bool TraverseQualifiedTypeLoc(QualifiedTypeLoc QTL) {
397
    return TraverseTypeLoc(QTL.getUnqualifiedLoc());
398
  }
399
  // Uninteresting parts of the AST that don't have locations within them.
400
  bool TraverseNestedNameSpecifier(NestedNameSpecifier *) { return true; }
401
  bool TraverseType(QualType) { return true; }
402

403
  // OpaqueValueExpr blocks traversal, we must explicitly traverse it.
404
  bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
405
    return TraverseStmt(E->getSourceExpr());
406
  }
407
  // We only want to traverse the *syntactic form* to understand the selection.
408
  bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
409
    return TraverseStmt(E->getSyntacticForm());
410
  }
411
};
412

413
} // namespace
414

415
ASTNode dumpAST(const DynTypedNode &N, const syntax::TokenBuffer &Tokens,
416
                const ASTContext &Ctx) {
417
  DumpVisitor V(Tokens, Ctx);
418
  // DynTypedNode only works with const, RecursiveASTVisitor only non-const :-(
419
  if (const auto *D = N.get<Decl>())
420
    V.TraverseDecl(const_cast<Decl *>(D));
421
  else if (const auto *S = N.get<Stmt>())
422
    V.TraverseStmt(const_cast<Stmt *>(S));
423
  else if (const auto *NNSL = N.get<NestedNameSpecifierLoc>())
424
    V.TraverseNestedNameSpecifierLoc(
425
        *const_cast<NestedNameSpecifierLoc *>(NNSL));
426
  else if (const auto *NNS = N.get<NestedNameSpecifier>())
427
    V.TraverseNestedNameSpecifier(const_cast<NestedNameSpecifier *>(NNS));
428
  else if (const auto *TL = N.get<TypeLoc>())
429
    V.TraverseTypeLoc(*const_cast<TypeLoc *>(TL));
430
  else if (const auto *QT = N.get<QualType>())
431
    V.TraverseType(*const_cast<QualType *>(QT));
432
  else if (const auto *CCI = N.get<CXXCtorInitializer>())
433
    V.TraverseConstructorInitializer(const_cast<CXXCtorInitializer *>(CCI));
434
  else if (const auto *TAL = N.get<TemplateArgumentLoc>())
435
    V.TraverseTemplateArgumentLoc(*const_cast<TemplateArgumentLoc *>(TAL));
436
  else if (const auto *CBS = N.get<CXXBaseSpecifier>())
437
    V.TraverseCXXBaseSpecifier(*const_cast<CXXBaseSpecifier *>(CBS));
438
  else if (const auto *CR = N.get<ConceptReference>())
439
    V.TraverseConceptReference(const_cast<ConceptReference *>(CR));
440
  else
441
    elog("dumpAST: unhandled DynTypedNode kind {0}",
442
         N.getNodeKind().asStringRef());
443
  return std::move(V.Root);
444
}
445

446
} // namespace clangd
447
} // namespace clang
448