Coverage Report

Created: 2022-07-16 07:03

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Tooling/Syntax/BuildTree.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- BuildTree.cpp ------------------------------------------*- 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
#include "clang/Tooling/Syntax/BuildTree.h"
9
#include "clang/AST/ASTFwd.h"
10
#include "clang/AST/Decl.h"
11
#include "clang/AST/DeclBase.h"
12
#include "clang/AST/DeclCXX.h"
13
#include "clang/AST/DeclarationName.h"
14
#include "clang/AST/Expr.h"
15
#include "clang/AST/ExprCXX.h"
16
#include "clang/AST/IgnoreExpr.h"
17
#include "clang/AST/OperationKinds.h"
18
#include "clang/AST/RecursiveASTVisitor.h"
19
#include "clang/AST/Stmt.h"
20
#include "clang/AST/TypeLoc.h"
21
#include "clang/AST/TypeLocVisitor.h"
22
#include "clang/Basic/LLVM.h"
23
#include "clang/Basic/SourceLocation.h"
24
#include "clang/Basic/SourceManager.h"
25
#include "clang/Basic/Specifiers.h"
26
#include "clang/Basic/TokenKinds.h"
27
#include "clang/Lex/Lexer.h"
28
#include "clang/Lex/LiteralSupport.h"
29
#include "clang/Tooling/Syntax/Nodes.h"
30
#include "clang/Tooling/Syntax/TokenBufferTokenManager.h"
31
#include "clang/Tooling/Syntax/Tokens.h"
32
#include "clang/Tooling/Syntax/Tree.h"
33
#include "llvm/ADT/ArrayRef.h"
34
#include "llvm/ADT/DenseMap.h"
35
#include "llvm/ADT/PointerUnion.h"
36
#include "llvm/ADT/STLExtras.h"
37
#include "llvm/ADT/ScopeExit.h"
38
#include "llvm/ADT/SmallVector.h"
39
#include "llvm/Support/Allocator.h"
40
#include "llvm/Support/Casting.h"
41
#include "llvm/Support/Compiler.h"
42
#include "llvm/Support/FormatVariadic.h"
43
#include "llvm/Support/MemoryBuffer.h"
44
#include "llvm/Support/raw_ostream.h"
45
#include <cstddef>
46
#include <map>
47
48
using namespace clang;
49
50
// Ignores the implicit `CXXConstructExpr` for copy/move constructor calls
51
// generated by the compiler, as well as in implicit conversions like the one
52
// wrapping `1` in `X x = 1;`.
53
11.3k
static Expr *IgnoreImplicitConstructorSingleStep(Expr *E) {
54
11.3k
  if (auto *C = dyn_cast<CXXConstructExpr>(E)) {
55
554
    auto NumArgs = C->getNumArgs();
56
554
    if (NumArgs == 1 || 
(330
NumArgs > 1330
&&
isa<CXXDefaultArgExpr>(C->getArg(1))216
)) {
57
300
      Expr *A = C->getArg(0);
58
300
      if (C->getParenOrBraceRange().isInvalid())
59
152
        return A;
60
300
    }
61
554
  }
62
11.2k
  return E;
63
11.3k
}
64
65
// In:
66
// struct X {
67
//   X(int)
68
// };
69
// X x = X(1);
70
// Ignores the implicit `CXXFunctionalCastExpr` that wraps
71
// `CXXConstructExpr X(1)`.
72
11.3k
static Expr *IgnoreCXXFunctionalCastExprWrappingConstructor(Expr *E) {
73
11.3k
  if (auto *F = dyn_cast<CXXFunctionalCastExpr>(E)) {
74
60
    if (F->getCastKind() == CK_ConstructorConversion)
75
30
      return F->getSubExpr();
76
60
  }
77
11.3k
  return E;
78
11.3k
}
79
80
9.33k
static Expr *IgnoreImplicit(Expr *E) {
81
9.33k
  return IgnoreExprNodes(E, IgnoreImplicitSingleStep,
82
9.33k
                         IgnoreImplicitConstructorSingleStep,
83
9.33k
                         IgnoreCXXFunctionalCastExprWrappingConstructor);
84
9.33k
}
85
86
LLVM_ATTRIBUTE_UNUSED
87
334
static bool isImplicitExpr(Expr *E) { return IgnoreImplicit(E) != E; }
88
89
namespace {
90
/// Get start location of the Declarator from the TypeLoc.
91
/// E.g.:
92
///   loc of `(` in `int (a)`
93
///   loc of `*` in `int *(a)`
94
///   loc of the first `(` in `int (*a)(int)`
95
///   loc of the `*` in `int *(a)(int)`
96
///   loc of the first `*` in `const int *const *volatile a;`
97
///
98
/// It is non-trivial to get the start location because TypeLocs are stored
99
/// inside out. In the example above `*volatile` is the TypeLoc returned
100
/// by `Decl.getTypeSourceInfo()`, and `*const` is what `.getPointeeLoc()`
101
/// returns.
102
struct GetStartLoc : TypeLocVisitor<GetStartLoc, SourceLocation> {
103
156
  SourceLocation VisitParenTypeLoc(ParenTypeLoc T) {
104
156
    auto L = Visit(T.getInnerLoc());
105
156
    if (L.isValid())
106
28
      return L;
107
128
    return T.getLParenLoc();
108
156
  }
109
110
  // Types spelled in the prefix part of the declarator.
111
448
  SourceLocation VisitPointerTypeLoc(PointerTypeLoc T) {
112
448
    return HandlePointer(T);
113
448
  }
114
115
70
  SourceLocation VisitMemberPointerTypeLoc(MemberPointerTypeLoc T) {
116
70
    return HandlePointer(T);
117
70
  }
118
119
0
  SourceLocation VisitBlockPointerTypeLoc(BlockPointerTypeLoc T) {
120
0
    return HandlePointer(T);
121
0
  }
122
123
158
  SourceLocation VisitReferenceTypeLoc(ReferenceTypeLoc T) {
124
158
    return HandlePointer(T);
125
158
  }
126
127
0
  SourceLocation VisitObjCObjectPointerTypeLoc(ObjCObjectPointerTypeLoc T) {
128
0
    return HandlePointer(T);
129
0
  }
130
131
  // All other cases are not important, as they are either part of declaration
132
  // specifiers (e.g. inheritors of TypeSpecTypeLoc) or introduce modifiers on
133
  // existing declarators (e.g. QualifiedTypeLoc). They cannot start the
134
  // declarator themselves, but their underlying type can.
135
7.42k
  SourceLocation VisitTypeLoc(TypeLoc T) {
136
7.42k
    auto N = T.getNextTypeLoc();
137
7.42k
    if (!N)
138
4.59k
      return SourceLocation();
139
2.82k
    return Visit(N);
140
7.42k
  }
141
142
2.22k
  SourceLocation VisitFunctionProtoTypeLoc(FunctionProtoTypeLoc T) {
143
2.22k
    if (T.getTypePtr()->hasTrailingReturn())
144
24
      return SourceLocation(); // avoid recursing into the suffix of declarator.
145
2.20k
    return VisitTypeLoc(T);
146
2.22k
  }
147
148
private:
149
676
  template <class PtrLoc> SourceLocation HandlePointer(PtrLoc T) {
150
676
    auto L = Visit(T.getPointeeLoc());
151
676
    if (L.isValid())
152
152
      return L;
153
524
    return T.getLocalSourceRange().getBegin();
154
676
  }
Unexecuted instantiation: BuildTree.cpp:clang::SourceLocation (anonymous namespace)::GetStartLoc::HandlePointer<clang::BlockPointerTypeLoc>(clang::BlockPointerTypeLoc)
BuildTree.cpp:clang::SourceLocation (anonymous namespace)::GetStartLoc::HandlePointer<clang::MemberPointerTypeLoc>(clang::MemberPointerTypeLoc)
Line
Count
Source
149
70
  template <class PtrLoc> SourceLocation HandlePointer(PtrLoc T) {
150
70
    auto L = Visit(T.getPointeeLoc());
151
70
    if (L.isValid())
152
40
      return L;
153
30
    return T.getLocalSourceRange().getBegin();
154
70
  }
Unexecuted instantiation: BuildTree.cpp:clang::SourceLocation (anonymous namespace)::GetStartLoc::HandlePointer<clang::ObjCObjectPointerTypeLoc>(clang::ObjCObjectPointerTypeLoc)
BuildTree.cpp:clang::SourceLocation (anonymous namespace)::GetStartLoc::HandlePointer<clang::PointerTypeLoc>(clang::PointerTypeLoc)
Line
Count
Source
149
448
  template <class PtrLoc> SourceLocation HandlePointer(PtrLoc T) {
150
448
    auto L = Visit(T.getPointeeLoc());
151
448
    if (L.isValid())
152
112
      return L;
153
336
    return T.getLocalSourceRange().getBegin();
154
448
  }
BuildTree.cpp:clang::SourceLocation (anonymous namespace)::GetStartLoc::HandlePointer<clang::ReferenceTypeLoc>(clang::ReferenceTypeLoc)
Line
Count
Source
149
158
  template <class PtrLoc> SourceLocation HandlePointer(PtrLoc T) {
150
158
    auto L = Visit(T.getPointeeLoc());
151
158
    if (L.isValid())
152
0
      return L;
153
158
    return T.getLocalSourceRange().getBegin();
154
158
  }
155
};
156
} // namespace
157
158
465
static CallExpr::arg_range dropDefaultArgs(CallExpr::arg_range Args) {
159
465
  auto FirstDefaultArg =
160
465
      llvm::find_if(Args, [](auto It) 
{ return isa<CXXDefaultArgExpr>(It); }198
);
161
465
  return llvm::make_range(Args.begin(), FirstDefaultArg);
162
465
}
163
164
130
static syntax::NodeKind getOperatorNodeKind(const CXXOperatorCallExpr &E) {
165
130
  switch (E.getOperator()) {
166
  // Comparison
167
0
  case OO_EqualEqual:
168
0
  case OO_ExclaimEqual:
169
0
  case OO_Greater:
170
0
  case OO_GreaterEqual:
171
10
  case OO_Less:
172
10
  case OO_LessEqual:
173
10
  case OO_Spaceship:
174
  // Assignment
175
20
  case OO_Equal:
176
20
  case OO_SlashEqual:
177
20
  case OO_PercentEqual:
178
20
  case OO_CaretEqual:
179
20
  case OO_PipeEqual:
180
20
  case OO_LessLessEqual:
181
20
  case OO_GreaterGreaterEqual:
182
20
  case OO_PlusEqual:
183
20
  case OO_MinusEqual:
184
20
  case OO_StarEqual:
185
20
  case OO_AmpEqual:
186
  // Binary computation
187
20
  case OO_Slash:
188
20
  case OO_Percent:
189
20
  case OO_Caret:
190
20
  case OO_Pipe:
191
30
  case OO_LessLess:
192
30
  case OO_GreaterGreater:
193
30
  case OO_AmpAmp:
194
30
  case OO_PipePipe:
195
30
  case OO_ArrowStar:
196
40
  case OO_Comma:
197
40
    return syntax::NodeKind::BinaryOperatorExpression;
198
0
  case OO_Tilde:
199
10
  case OO_Exclaim:
200
10
    return syntax::NodeKind::PrefixUnaryOperatorExpression;
201
  // Prefix/Postfix increment/decrement
202
30
  case OO_PlusPlus:
203
30
  case OO_MinusMinus:
204
30
    switch (E.getNumArgs()) {
205
10
    case 1:
206
10
      return syntax::NodeKind::PrefixUnaryOperatorExpression;
207
20
    case 2:
208
20
      return syntax::NodeKind::PostfixUnaryOperatorExpression;
209
0
    default:
210
0
      llvm_unreachable("Invalid number of arguments for operator");
211
30
    }
212
  // Operators that can be unary or binary
213
10
  case OO_Plus:
214
10
  case OO_Minus:
215
10
  case OO_Star:
216
20
  case OO_Amp:
217
20
    switch (E.getNumArgs()) {
218
10
    case 1:
219
10
      return syntax::NodeKind::PrefixUnaryOperatorExpression;
220
10
    case 2:
221
10
      return syntax::NodeKind::BinaryOperatorExpression;
222
0
    default:
223
0
      llvm_unreachable("Invalid number of arguments for operator");
224
20
    }
225
0
    return syntax::NodeKind::BinaryOperatorExpression;
226
  // Not yet supported by SyntaxTree
227
0
  case OO_New:
228
0
  case OO_Delete:
229
0
  case OO_Array_New:
230
0
  case OO_Array_Delete:
231
0
  case OO_Coawait:
232
0
  case OO_Subscript:
233
0
  case OO_Arrow:
234
0
    return syntax::NodeKind::UnknownExpression;
235
30
  case OO_Call:
236
30
    return syntax::NodeKind::CallExpression;
237
0
  case OO_Conditional: // not overloadable
238
0
  case NUM_OVERLOADED_OPERATORS:
239
0
  case OO_None:
240
0
    llvm_unreachable("Not an overloadable operator");
241
130
  }
242
0
  llvm_unreachable("Unknown OverloadedOperatorKind enum");
243
0
}
244
245
/// Get the start of the qualified name. In the examples below it gives the
246
/// location of the `^`:
247
///     `int ^a;`
248
///     `int *^a;`
249
///     `int ^a::S::f(){}`
250
4.59k
static SourceLocation getQualifiedNameStart(NamedDecl *D) {
251
4.59k
  assert((isa<DeclaratorDecl, TypedefNameDecl>(D)) &&
252
4.59k
         "only DeclaratorDecl and TypedefNameDecl are supported.");
253
254
0
  auto DN = D->getDeclName();
255
4.59k
  bool IsAnonymous = DN.isIdentifier() && 
!DN.getAsIdentifierInfo()4.18k
;
256
4.59k
  if (IsAnonymous)
257
708
    return SourceLocation();
258
259
3.88k
  if (const auto *DD = dyn_cast<DeclaratorDecl>(D)) {
260
3.81k
    if (DD->getQualifierLoc()) {
261
8
      return DD->getQualifierLoc().getBeginLoc();
262
8
    }
263
3.81k
  }
264
265
3.88k
  return D->getLocation();
266
3.88k
}
267
268
/// Gets the range of the initializer inside an init-declarator C++ [dcl.decl].
269
///     `int a;` -> range of ``,
270
///     `int *a = nullptr` -> range of `= nullptr`.
271
///     `int a{}` -> range of `{}`.
272
///     `int a()` -> range of `()`.
273
4.59k
static SourceRange getInitializerRange(Decl *D) {
274
4.59k
  if (auto *V = dyn_cast<VarDecl>(D)) {
275
2.18k
    auto *I = V->getInit();
276
    // Initializers in range-based-for are not part of the declarator
277
2.18k
    if (I && 
!V->isCXXForRangeDecl()372
)
278
364
      return I->getSourceRange();
279
2.18k
  }
280
281
4.23k
  return SourceRange();
282
4.59k
}
283
284
/// Gets the range of declarator as defined by the C++ grammar. E.g.
285
///     `int a;` -> range of `a`,
286
///     `int *a;` -> range of `*a`,
287
///     `int a[10];` -> range of `a[10]`,
288
///     `int a[1][2][3];` -> range of `a[1][2][3]`,
289
///     `int *a = nullptr` -> range of `*a = nullptr`.
290
///     `int S::f(){}` -> range of `S::f()`.
291
/// FIXME: \p Name must be a source range.
292
static SourceRange getDeclaratorRange(const SourceManager &SM, TypeLoc T,
293
                                      SourceLocation Name,
294
4.59k
                                      SourceRange Initializer) {
295
4.59k
  SourceLocation Start = GetStartLoc().Visit(T);
296
4.59k
  SourceLocation End = T.getEndLoc();
297
4.59k
  if (Name.isValid()) {
298
3.88k
    if (Start.isInvalid())
299
3.43k
      Start = Name;
300
    // End of TypeLoc could be invalid if the type is invalid, fallback to the
301
    // NameLoc.
302
3.88k
    if (End.isInvalid() || 
SM.isBeforeInTranslationUnit(End, Name)3.87k
)
303
1.47k
      End = Name;
304
3.88k
  }
305
4.59k
  if (Initializer.isValid()) {
306
364
    auto InitializerEnd = Initializer.getEnd();
307
364
    assert(SM.isBeforeInTranslationUnit(End, InitializerEnd) ||
308
364
           End == InitializerEnd);
309
0
    End = InitializerEnd;
310
364
  }
311
0
  return SourceRange(Start, End);
312
4.59k
}
313
314
namespace {
315
/// All AST hierarchy roots that can be represented as pointers.
316
using ASTPtr = llvm::PointerUnion<Stmt *, Decl *>;
317
/// Maintains a mapping from AST to syntax tree nodes. This class will get more
318
/// complicated as we support more kinds of AST nodes, e.g. TypeLocs.
319
/// FIXME: expose this as public API.
320
class ASTToSyntaxMapping {
321
public:
322
12.1k
  void add(ASTPtr From, syntax::Tree *To) {
323
12.1k
    assert(To != nullptr);
324
0
    assert(!From.isNull());
325
326
0
    bool Added = Nodes.insert({From, To}).second;
327
12.1k
    (void)Added;
328
12.1k
    assert(Added && "mapping added twice");
329
12.1k
  }
330
331
201
  void add(NestedNameSpecifierLoc From, syntax::Tree *To) {
332
201
    assert(To != nullptr);
333
0
    assert(From.hasQualifier());
334
335
0
    bool Added = NNSNodes.insert({From, To}).second;
336
201
    (void)Added;
337
201
    assert(Added && "mapping added twice");
338
201
  }
339
340
6.31k
  syntax::Tree *find(ASTPtr P) const { return Nodes.lookup(P); }
341
342
103
  syntax::Tree *find(NestedNameSpecifierLoc P) const {
343
103
    return NNSNodes.lookup(P);
344
103
  }
345
346
private:
347
  llvm::DenseMap<ASTPtr, syntax::Tree *> Nodes;
348
  llvm::DenseMap<NestedNameSpecifierLoc, syntax::Tree *> NNSNodes;
349
};
350
} // namespace
351
352
/// A helper class for constructing the syntax tree while traversing a clang
353
/// AST.
354
///
355
/// At each point of the traversal we maintain a list of pending nodes.
356
/// Initially all tokens are added as pending nodes. When processing a clang AST
357
/// node, the clients need to:
358
///   - create a corresponding syntax node,
359
///   - assign roles to all pending child nodes with 'markChild' and
360
///     'markChildToken',
361
///   - replace the child nodes with the new syntax node in the pending list
362
///     with 'foldNode'.
363
///
364
/// Note that all children are expected to be processed when building a node.
365
///
366
/// Call finalize() to finish building the tree and consume the root node.
367
class syntax::TreeBuilder {
368
public:
369
  TreeBuilder(syntax::Arena &Arena, TokenBufferTokenManager& TBTM)
370
      : Arena(Arena),
371
        TBTM(TBTM),
372
2.16k
        Pending(Arena, TBTM.tokenBuffer()) {
373
2.16k
    for (const auto &T : TBTM.tokenBuffer().expandedTokens())
374
39.5k
      LocationToToken.insert({T.location(), &T});
375
2.16k
  }
376
377
30.7k
  llvm::BumpPtrAllocator &allocator() { return Arena.getAllocator(); }
378
4.59k
  const SourceManager &sourceManager() const {
379
4.59k
    return TBTM.sourceManager();
380
4.59k
  }
381
382
  /// Populate children for \p New node, assuming it covers tokens from \p
383
  /// Range.
384
22.7k
  void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New, ASTPtr From) {
385
22.7k
    assert(New);
386
0
    Pending.foldChildren(TBTM.tokenBuffer(), Range, New);
387
22.7k
    if (From)
388
12.1k
      Mapping.add(From, New);
389
22.7k
  }
390
391
2.67k
  void foldNode(ArrayRef<syntax::Token> Range, syntax::Tree *New, TypeLoc L) {
392
    // FIXME: add mapping for TypeLocs
393
2.67k
    foldNode(Range, New, nullptr);
394
2.67k
  }
395
396
  void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
397
201
                NestedNameSpecifierLoc From) {
398
201
    assert(New);
399
0
    Pending.foldChildren(TBTM.tokenBuffer(), Range, New);
400
201
    if (From)
401
201
      Mapping.add(From, New);
402
201
  }
403
404
  /// Populate children for \p New list, assuming it covers tokens from a
405
  /// subrange of \p SuperRange.
406
  void foldList(ArrayRef<syntax::Token> SuperRange, syntax::List *New,
407
3.99k
                ASTPtr From) {
408
3.99k
    assert(New);
409
0
    auto ListRange = Pending.shrinkToFitList(SuperRange);
410
3.99k
    Pending.foldChildren(TBTM.tokenBuffer(), ListRange, New);
411
3.99k
    if (From)
412
0
      Mapping.add(From, New);
413
3.99k
  }
414
415
  /// Notifies that we should not consume trailing semicolon when computing
416
  /// token range of \p D.
417
  void noticeDeclWithoutSemicolon(Decl *D);
418
419
  /// Mark the \p Child node with a corresponding \p Role. All marked children
420
  /// should be consumed by foldNode.
421
  /// When called on expressions (clang::Expr is derived from clang::Stmt),
422
  /// wraps expressions into expression statement.
423
  void markStmtChild(Stmt *Child, NodeRole Role);
424
  /// Should be called for expressions in non-statement position to avoid
425
  /// wrapping into expression statement.
426
  void markExprChild(Expr *Child, NodeRole Role);
427
  /// Set role for a token starting at \p Loc.
428
  void markChildToken(SourceLocation Loc, NodeRole R);
429
  /// Set role for \p T.
430
  void markChildToken(const syntax::Token *T, NodeRole R);
431
432
  /// Set role for \p N.
433
  void markChild(syntax::Node *N, NodeRole R);
434
  /// Set role for the syntax node matching \p N.
435
  void markChild(ASTPtr N, NodeRole R);
436
  /// Set role for the syntax node matching \p N.
437
  void markChild(NestedNameSpecifierLoc N, NodeRole R);
438
439
  /// Finish building the tree and consume the root node.
440
2.16k
  syntax::TranslationUnit *finalize() && {
441
2.16k
    auto Tokens = TBTM.tokenBuffer().expandedTokens();
442
2.16k
    assert(!Tokens.empty());
443
0
    assert(Tokens.back().kind() == tok::eof);
444
445
    // Build the root of the tree, consuming all the children.
446
0
    Pending.foldChildren(TBTM.tokenBuffer(), Tokens.drop_back(),
447
2.16k
                         new (Arena.getAllocator()) syntax::TranslationUnit);
448
449
2.16k
    auto *TU = cast<syntax::TranslationUnit>(std::move(Pending).finalize());
450
2.16k
    TU->assertInvariantsRecursive();
451
2.16k
    return TU;
452
2.16k
  }
453
454
  /// Finds a token starting at \p L. The token must exist if \p L is valid.
455
  const syntax::Token *findToken(SourceLocation L) const;
456
457
  /// Finds the syntax tokens corresponding to the \p SourceRange.
458
18.8k
  ArrayRef<syntax::Token> getRange(SourceRange Range) const {
459
18.8k
    assert(Range.isValid());
460
0
    return getRange(Range.getBegin(), Range.getEnd());
461
18.8k
  }
462
463
  /// Finds the syntax tokens corresponding to the passed source locations.
464
  /// \p First is the start position of the first token and \p Last is the start
465
  /// position of the last token.
466
  ArrayRef<syntax::Token> getRange(SourceLocation First,
467
24.8k
                                   SourceLocation Last) const {
468
24.8k
    assert(First.isValid());
469
0
    assert(Last.isValid());
470
0
    assert(First == Last ||
471
24.8k
           TBTM.sourceManager().isBeforeInTranslationUnit(First, Last));
472
0
    return llvm::makeArrayRef(findToken(First), std::next(findToken(Last)));
473
24.8k
  }
474
475
  ArrayRef<syntax::Token>
476
20
  getTemplateRange(const ClassTemplateSpecializationDecl *D) const {
477
20
    auto Tokens = getRange(D->getSourceRange());
478
20
    return maybeAppendSemicolon(Tokens, D);
479
20
  }
480
481
  /// Returns true if \p D is the last declarator in a chain and is thus
482
  /// reponsible for creating SimpleDeclaration for the whole chain.
483
4.06k
  bool isResponsibleForCreatingDeclaration(const Decl *D) const {
484
4.06k
    assert((isa<DeclaratorDecl, TypedefNameDecl>(D)) &&
485
4.06k
           "only DeclaratorDecl and TypedefNameDecl are supported.");
486
487
0
    const Decl *Next = D->getNextDeclInContext();
488
489
    // There's no next sibling, this one is responsible.
490
4.06k
    if (Next == nullptr) {
491
3.02k
      return true;
492
3.02k
    }
493
494
    // Next sibling is not the same type, this one is responsible.
495
1.04k
    if (D->getKind() != Next->getKind()) {
496
172
      return true;
497
172
    }
498
    // Next sibling doesn't begin at the same loc, it must be a different
499
    // declaration, so this declarator is responsible.
500
872
    if (Next->getBeginLoc() != D->getBeginLoc()) {
501
802
      return true;
502
802
    }
503
504
    // NextT is a member of the same declaration, and we need the last member to
505
    // create declaration. This one is not responsible.
506
70
    return false;
507
872
  }
508
509
6.46k
  ArrayRef<syntax::Token> getDeclarationRange(Decl *D) {
510
6.46k
    ArrayRef<syntax::Token> Tokens;
511
    // We want to drop the template parameters for specializations.
512
6.46k
    if (const auto *S = dyn_cast<TagDecl>(D))
513
984
      Tokens = getRange(S->TypeDecl::getBeginLoc(), S->getEndLoc());
514
5.48k
    else
515
5.48k
      Tokens = getRange(D->getSourceRange());
516
6.46k
    return maybeAppendSemicolon(Tokens, D);
517
6.46k
  }
518
519
3.32k
  ArrayRef<syntax::Token> getExprRange(const Expr *E) const {
520
3.32k
    return getRange(E->getSourceRange());
521
3.32k
  }
522
523
  /// Find the adjusted range for the statement, consuming the trailing
524
  /// semicolon when needed.
525
3.62k
  ArrayRef<syntax::Token> getStmtRange(const Stmt *S) const {
526
3.62k
    auto Tokens = getRange(S->getSourceRange());
527
3.62k
    if (isa<CompoundStmt>(S))
528
1.43k
      return Tokens;
529
530
    // Some statements miss a trailing semicolon, e.g. 'return', 'continue' and
531
    // all statements that end with those. Consume this semicolon here.
532
2.19k
    if (Tokens.back().kind() == tok::semi)
533
264
      return Tokens;
534
1.92k
    return withTrailingSemicolon(Tokens);
535
2.19k
  }
536
537
private:
538
  ArrayRef<syntax::Token> maybeAppendSemicolon(ArrayRef<syntax::Token> Tokens,
539
6.48k
                                               const Decl *D) const {
540
6.48k
    if (isa<NamespaceDecl>(D))
541
98
      return Tokens;
542
6.39k
    if (DeclsWithoutSemicolons.count(D))
543
196
      return Tokens;
544
    // FIXME: do not consume trailing semicolon on function definitions.
545
    // Most declarations own a semicolon in syntax trees, but not in clang AST.
546
6.19k
    return withTrailingSemicolon(Tokens);
547
6.39k
  }
548
549
  ArrayRef<syntax::Token>
550
8.12k
  withTrailingSemicolon(ArrayRef<syntax::Token> Tokens) const {
551
8.12k
    assert(!Tokens.empty());
552
0
    assert(Tokens.back().kind() != tok::eof);
553
    // We never consume 'eof', so looking at the next token is ok.
554
8.12k
    if (Tokens.back().kind() != tok::semi && 
Tokens.end()->kind() == tok::semi8.11k
)
555
4.80k
      return llvm::makeArrayRef(Tokens.begin(), Tokens.end() + 1);
556
3.32k
    return Tokens;
557
8.12k
  }
558
559
21.5k
  void setRole(syntax::Node *N, NodeRole R) {
560
21.5k
    assert(N->getRole() == NodeRole::Detached);
561
0
    N->setRole(R);
562
21.5k
  }
563
564
  /// A collection of trees covering the input tokens.
565
  /// When created, each tree corresponds to a single token in the file.
566
  /// Clients call 'foldChildren' to attach one or more subtrees to a parent
567
  /// node and update the list of trees accordingly.
568
  ///
569
  /// Ensures that added nodes properly nest and cover the whole token stream.
570
  struct Forest {
571
2.16k
    Forest(syntax::Arena &A, const syntax::TokenBuffer &TB) {
572
2.16k
      assert(!TB.expandedTokens().empty());
573
0
      assert(TB.expandedTokens().back().kind() == tok::eof);
574
      // Create all leaf nodes.
575
      // Note that we do not have 'eof' in the tree.
576
37.3k
      for (const auto &T : TB.expandedTokens().drop_back()) {
577
37.3k
        auto *L = new (A.getAllocator())
578
37.3k
            syntax::Leaf(reinterpret_cast<TokenManager::Key>(&T));
579
37.3k
        L->Original = true;
580
37.3k
        L->CanModify = TB.spelledForExpanded(T).has_value();
581
37.3k
        Trees.insert(Trees.end(), {&T, L});
582
37.3k
      }
583
2.16k
    }
584
585
13.7k
    void assignRole(ArrayRef<syntax::Token> Range, syntax::NodeRole Role) {
586
13.7k
      assert(!Range.empty());
587
0
      auto It = Trees.lower_bound(Range.begin());
588
13.7k
      assert(It != Trees.end() && "no node found");
589
0
      assert(It->first == Range.begin() && "no child with the specified range");
590
0
      assert((std::next(It) == Trees.end() ||
591
13.7k
              std::next(It)->first == Range.end()) &&
592
13.7k
             "no child with the specified range");
593
0
      assert(It->second->getRole() == NodeRole::Detached &&
594
13.7k
             "re-assigning role for a child");
595
0
      It->second->setRole(Role);
596
13.7k
    }
597
598
    /// Shrink \p Range to a subrange that only contains tokens of a list.
599
    /// List elements and delimiters should already have correct roles.
600
3.99k
    ArrayRef<syntax::Token> shrinkToFitList(ArrayRef<syntax::Token> Range) {
601
3.99k
      auto BeginChildren = Trees.lower_bound(Range.begin());
602
3.99k
      assert((BeginChildren == Trees.end() ||
603
3.99k
              BeginChildren->first == Range.begin()) &&
604
3.99k
             "Range crosses boundaries of existing subtrees");
605
606
0
      auto EndChildren = Trees.lower_bound(Range.end());
607
3.99k
      assert(
608
3.99k
          (EndChildren == Trees.end() || EndChildren->first == Range.end()) &&
609
3.99k
          "Range crosses boundaries of existing subtrees");
610
611
15.4k
      auto BelongsToList = [](decltype(Trees)::value_type KV) {
612
15.4k
        auto Role = KV.second->getRole();
613
15.4k
        return Role == syntax::NodeRole::ListElement ||
614
15.4k
               
Role == syntax::NodeRole::ListDelimiter7.42k
;
615
15.4k
      };
616
617
3.99k
      auto BeginListChildren =
618
3.99k
          std::find_if(BeginChildren, EndChildren, BelongsToList);
619
620
3.99k
      auto EndListChildren =
621
3.99k
          std::find_if_not(BeginListChildren, EndChildren, BelongsToList);
622
623
3.99k
      return ArrayRef<syntax::Token>(BeginListChildren->first,
624
3.99k
                                     EndListChildren->first);
625
3.99k
    }
626
627
    /// Add \p Node to the forest and attach child nodes based on \p Tokens.
628
    void foldChildren(const syntax::TokenBuffer &TB,
629
30.7k
                      ArrayRef<syntax::Token> Tokens, syntax::Tree *Node) {
630
      // Attach children to `Node`.
631
30.7k
      assert(Node->getFirstChild() == nullptr && "node already has children");
632
633
0
      auto *FirstToken = Tokens.begin();
634
30.7k
      auto BeginChildren = Trees.lower_bound(FirstToken);
635
636
30.7k
      assert((BeginChildren == Trees.end() ||
637
30.7k
              BeginChildren->first == FirstToken) &&
638
30.7k
             "fold crosses boundaries of existing subtrees");
639
0
      auto EndChildren = Trees.lower_bound(Tokens.end());
640
30.7k
      assert(
641
30.7k
          (EndChildren == Trees.end() || EndChildren->first == Tokens.end()) &&
642
30.7k
          "fold crosses boundaries of existing subtrees");
643
644
96.6k
      for (auto It = BeginChildren; It != EndChildren; 
++It65.9k
) {
645
65.9k
        auto *C = It->second;
646
65.9k
        if (C->getRole() == NodeRole::Detached)
647
32.7k
          C->setRole(NodeRole::Unknown);
648
65.9k
        Node->appendChildLowLevel(C);
649
65.9k
      }
650
651
      // Mark that this node came from the AST and is backed by the source code.
652
30.7k
      Node->Original = true;
653
30.7k
      Node->CanModify =
654
30.7k
          TB.spelledForExpanded(Tokens).has_value();
655
656
30.7k
      Trees.erase(BeginChildren, EndChildren);
657
30.7k
      Trees.insert({FirstToken, Node});
658
30.7k
    }
659
660
    // EXPECTS: all tokens were consumed and are owned by a single root node.
661
2.16k
    syntax::Node *finalize() && {
662
2.16k
      assert(Trees.size() == 1);
663
0
      auto *Root = Trees.begin()->second;
664
2.16k
      Trees = {};
665
2.16k
      return Root;
666
2.16k
    }
667
668
0
    std::string str(const syntax::TokenBufferTokenManager &STM) const {
669
0
      std::string R;
670
0
      for (auto It = Trees.begin(); It != Trees.end(); ++It) {
671
0
        unsigned CoveredTokens =
672
0
            It != Trees.end()
673
0
                ? (std::next(It)->first - It->first)
674
0
                : STM.tokenBuffer().expandedTokens().end() - It->first;
675
0
676
0
        R += std::string(
677
0
            formatv("- '{0}' covers '{1}'+{2} tokens\n", It->second->getKind(),
678
0
                    It->first->text(STM.sourceManager()), CoveredTokens));
679
0
        R += It->second->dump(STM);
680
0
      }
681
0
      return R;
682
0
    }
683
684
  private:
685
    /// Maps from the start token to a subtree starting at that token.
686
    /// Keys in the map are pointers into the array of expanded tokens, so
687
    /// pointer order corresponds to the order of preprocessor tokens.
688
    std::map<const syntax::Token *, syntax::Node *> Trees;
689
  };
690
691
  /// For debugging purposes.
692
0
  std::string str() { return Pending.str(TBTM); }
693
694
  syntax::Arena &Arena;
695
  TokenBufferTokenManager& TBTM;
696
  /// To quickly find tokens by their start location.
697
  llvm::DenseMap<SourceLocation, const syntax::Token *> LocationToToken;
698
  Forest Pending;
699
  llvm::DenseSet<Decl *> DeclsWithoutSemicolons;
700
  ASTToSyntaxMapping Mapping;
701
};
702
703
namespace {
704
class BuildTreeVisitor : public RecursiveASTVisitor<BuildTreeVisitor> {
705
public:
706
  explicit BuildTreeVisitor(ASTContext &Context, syntax::TreeBuilder &Builder)
707
2.16k
      : Builder(Builder), Context(Context) {}
708
709
47.2k
  bool shouldTraversePostOrder() const { return true; }
710
711
4.52k
  bool WalkUpFromDeclaratorDecl(DeclaratorDecl *DD) {
712
4.52k
    return processDeclaratorAndDeclaration(DD);
713
4.52k
  }
714
715
72
  bool WalkUpFromTypedefNameDecl(TypedefNameDecl *TD) {
716
72
    return processDeclaratorAndDeclaration(TD);
717
72
  }
718
719
331
  bool VisitDecl(Decl *D) {
720
331
    assert(!D->isImplicit());
721
0
    Builder.foldNode(Builder.getDeclarationRange(D),
722
331
                     new (allocator()) syntax::UnknownDeclaration(), D);
723
331
    return true;
724
331
  }
725
726
  // RAV does not call WalkUpFrom* on explicit instantiations, so we have to
727
  // override Traverse.
728
  // FIXME: make RAV call WalkUpFrom* instead.
729
  bool
730
30
  TraverseClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *C) {
731
30
    if (!RecursiveASTVisitor::TraverseClassTemplateSpecializationDecl(C))
732
0
      return false;
733
30
    if (C->isExplicitSpecialization())
734
10
      return true; // we are only interested in explicit instantiations.
735
20
    auto *Declaration =
736
20
        cast<syntax::SimpleDeclaration>(handleFreeStandingTagDecl(C));
737
20
    foldExplicitTemplateInstantiation(
738
20
        Builder.getTemplateRange(C), Builder.findToken(C->getExternLoc()),
739
20
        Builder.findToken(C->getTemplateKeywordLoc()), Declaration, C);
740
20
    return true;
741
30
  }
742
743
273
  bool WalkUpFromTemplateDecl(TemplateDecl *S) {
744
273
    foldTemplateDeclaration(
745
273
        Builder.getDeclarationRange(S),
746
273
        Builder.findToken(S->getTemplateParameters()->getTemplateLoc()),
747
273
        Builder.getDeclarationRange(S->getTemplatedDecl()), S);
748
273
    return true;
749
273
  }
750
751
886
  bool WalkUpFromTagDecl(TagDecl *C) {
752
    // FIXME: build the ClassSpecifier node.
753
886
    if (!C->isFreeStanding()) {
754
42
      assert(C->getNumTemplateParameterLists() == 0);
755
0
      return true;
756
42
    }
757
844
    handleFreeStandingTagDecl(C);
758
844
    return true;
759
886
  }
760
761
864
  syntax::Declaration *handleFreeStandingTagDecl(TagDecl *C) {
762
864
    assert(C->isFreeStanding());
763
    // Class is a declaration specifier and needs a spanning declaration node.
764
0
    auto DeclarationRange = Builder.getDeclarationRange(C);
765
864
    syntax::Declaration *Result = new (allocator()) syntax::SimpleDeclaration;
766
864
    Builder.foldNode(DeclarationRange, Result, nullptr);
767
768
    // Build TemplateDeclaration nodes if we had template parameters.
769
864
    auto ConsumeTemplateParameters = [&](const TemplateParameterList &L) {
770
30
      const auto *TemplateKW = Builder.findToken(L.getTemplateLoc());
771
30
      auto R = llvm::makeArrayRef(TemplateKW, DeclarationRange.end());
772
30
      Result =
773
30
          foldTemplateDeclaration(R, TemplateKW, DeclarationRange, nullptr);
774
30
      DeclarationRange = R;
775
30
    };
776
864
    if (auto *S = dyn_cast<ClassTemplatePartialSpecializationDecl>(C))
777
10
      ConsumeTemplateParameters(*S->getTemplateParameters());
778
884
    for (unsigned I = C->getNumTemplateParameterLists(); 0 < I; 
--I20
)
779
20
      ConsumeTemplateParameters(*C->getTemplateParameterList(I - 1));
780
864
    return Result;
781
864
  }
782
783
2.16k
  bool WalkUpFromTranslationUnitDecl(TranslationUnitDecl *TU) {
784
    // We do not want to call VisitDecl(), the declaration for translation
785
    // unit is built by finalize().
786
2.16k
    return true;
787
2.16k
  }
788
789
1.43k
  bool WalkUpFromCompoundStmt(CompoundStmt *S) {
790
1.43k
    using NodeRole = syntax::NodeRole;
791
792
1.43k
    Builder.markChildToken(S->getLBracLoc(), NodeRole::OpenParen);
793
1.43k
    for (auto *Child : S->body())
794
2.00k
      Builder.markStmtChild(Child, NodeRole::Statement);
795
1.43k
    Builder.markChildToken(S->getRBracLoc(), NodeRole::CloseParen);
796
797
1.43k
    Builder.foldNode(Builder.getStmtRange(S),
798
1.43k
                     new (allocator()) syntax::CompoundStatement, S);
799
1.43k
    return true;
800
1.43k
  }
801
802
  // Some statements are not yet handled by syntax trees.
803
14
  bool WalkUpFromStmt(Stmt *S) {
804
14
    Builder.foldNode(Builder.getStmtRange(S),
805
14
                     new (allocator()) syntax::UnknownStatement, S);
806
14
    return true;
807
14
  }
808
809
120
  bool TraverseIfStmt(IfStmt *S) {
810
120
    bool Result = [&, this]() {
811
120
      if (S->getInit() && 
!TraverseStmt(S->getInit())4
) {
812
0
        return false;
813
0
      }
814
      // In cases where the condition is an initialized declaration in a
815
      // statement, we want to preserve the declaration and ignore the
816
      // implicit condition expression in the syntax tree.
817
120
      if (S->hasVarStorage()) {
818
4
        if (!TraverseStmt(S->getConditionVariableDeclStmt()))
819
0
          return false;
820
116
      } else if (S->getCond() && !TraverseStmt(S->getCond()))
821
0
        return false;
822
823
120
      if (S->getThen() && !TraverseStmt(S->getThen()))
824
0
        return false;
825
120
      if (S->getElse() && 
!TraverseStmt(S->getElse())84
)
826
0
        return false;
827
120
      return true;
828
120
    }();
829
120
    WalkUpFromIfStmt(S);
830
120
    return Result;
831
120
  }
832
833
8
  bool TraverseCXXForRangeStmt(CXXForRangeStmt *S) {
834
    // We override to traverse range initializer as VarDecl.
835
    // RAV traverses it as a statement, we produce invalid node kinds in that
836
    // case.
837
    // FIXME: should do this in RAV instead?
838
8
    bool Result = [&, this]() {
839
8
      if (S->getInit() && 
!TraverseStmt(S->getInit())0
)
840
0
        return false;
841
8
      if (S->getLoopVariable() && !TraverseDecl(S->getLoopVariable()))
842
0
        return false;
843
8
      if (S->getRangeInit() && !TraverseStmt(S->getRangeInit()))
844
0
        return false;
845
8
      if (S->getBody() && !TraverseStmt(S->getBody()))
846
0
        return false;
847
8
      return true;
848
8
    }();
849
8
    WalkUpFromCXXForRangeStmt(S);
850
8
    return Result;
851
8
  }
852
853
7.40k
  bool TraverseStmt(Stmt *S) {
854
7.40k
    if (auto *DS = dyn_cast_or_null<DeclStmt>(S)) {
855
      // We want to consume the semicolon, make sure SimpleDeclaration does not.
856
196
      for (auto *D : DS->decls())
857
224
        Builder.noticeDeclWithoutSemicolon(D);
858
7.20k
    } else if (auto *E = dyn_cast_or_null<Expr>(S)) {
859
4.94k
      return RecursiveASTVisitor::TraverseStmt(IgnoreImplicit(E));
860
4.94k
    }
861
2.45k
    return RecursiveASTVisitor::TraverseStmt(S);
862
7.40k
  }
863
864
28
  bool TraverseOpaqueValueExpr(OpaqueValueExpr *VE) {
865
    // OpaqueValue doesn't correspond to concrete syntax, ignore it.
866
28
    return true;
867
28
  }
868
869
  // Some expressions are not yet handled by syntax trees.
870
334
  bool WalkUpFromExpr(Expr *E) {
871
334
    assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");
872
0
    Builder.foldNode(Builder.getExprRange(E),
873
334
                     new (allocator()) syntax::UnknownExpression, E);
874
334
    return true;
875
334
  }
876
877
64
  bool TraverseUserDefinedLiteral(UserDefinedLiteral *S) {
878
    // The semantic AST node `UserDefinedLiteral` (UDL) may have one child node
879
    // referencing the location of the UDL suffix (`_w` in `1.2_w`). The
880
    // UDL suffix location does not point to the beginning of a token, so we
881
    // can't represent the UDL suffix as a separate syntax tree node.
882
883
64
    return WalkUpFromUserDefinedLiteral(S);
884
64
  }
885
886
  syntax::UserDefinedLiteralExpression *
887
64
  buildUserDefinedLiteral(UserDefinedLiteral *S) {
888
64
    switch (S->getLiteralOperatorKind()) {
889
8
    case UserDefinedLiteral::LOK_Integer:
890
8
      return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;
891
8
    case UserDefinedLiteral::LOK_Floating:
892
8
      return new (allocator()) syntax::FloatUserDefinedLiteralExpression;
893
8
    case UserDefinedLiteral::LOK_Character:
894
8
      return new (allocator()) syntax::CharUserDefinedLiteralExpression;
895
8
    case UserDefinedLiteral::LOK_String:
896
8
      return new (allocator()) syntax::StringUserDefinedLiteralExpression;
897
16
    case UserDefinedLiteral::LOK_Raw:
898
32
    case UserDefinedLiteral::LOK_Template:
899
      // For raw literal operator and numeric literal operator template we
900
      // cannot get the type of the operand in the semantic AST. We get this
901
      // information from the token. As integer and floating point have the same
902
      // token kind, we run `NumericLiteralParser` again to distinguish them.
903
32
      auto TokLoc = S->getBeginLoc();
904
32
      auto TokSpelling =
905
32
          Builder.findToken(TokLoc)->text(Context.getSourceManager());
906
32
      auto Literal =
907
32
          NumericLiteralParser(TokSpelling, TokLoc, Context.getSourceManager(),
908
32
                               Context.getLangOpts(), Context.getTargetInfo(),
909
32
                               Context.getDiagnostics());
910
32
      if (Literal.isIntegerLiteral())
911
16
        return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;
912
16
      else {
913
16
        assert(Literal.isFloatingLiteral());
914
0
        return new (allocator()) syntax::FloatUserDefinedLiteralExpression;
915
16
      }
916
64
    }
917
0
    llvm_unreachable("Unknown literal operator kind.");
918
0
  }
919
920
64
  bool WalkUpFromUserDefinedLiteral(UserDefinedLiteral *S) {
921
64
    Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);
922
64
    Builder.foldNode(Builder.getExprRange(S), buildUserDefinedLiteral(S), S);
923
64
    return true;
924
64
  }
925
926
  // FIXME: Fix `NestedNameSpecifierLoc::getLocalSourceRange` for the
927
  // `DependentTemplateSpecializationType` case.
928
  /// Given a nested-name-specifier return the range for the last name
929
  /// specifier.
930
  ///
931
  /// e.g. `std::T::template X<U>::` => `template X<U>::`
932
271
  SourceRange getLocalSourceRange(const NestedNameSpecifierLoc &NNSLoc) {
933
271
    auto SR = NNSLoc.getLocalSourceRange();
934
935
    // The method `NestedNameSpecifierLoc::getLocalSourceRange` *should*
936
    // return the desired `SourceRange`, but there is a corner case. For a
937
    // `DependentTemplateSpecializationType` this method returns its
938
    // qualifiers as well, in other words in the example above this method
939
    // returns `T::template X<U>::` instead of only `template X<U>::`
940
271
    if (auto TL = NNSLoc.getTypeLoc()) {
941
166
      if (auto DependentTL =
942
166
              TL.getAs<DependentTemplateSpecializationTypeLoc>()) {
943
        // The 'template' keyword is always present in dependent template
944
        // specializations. Except in the case of incorrect code
945
        // TODO: Treat the case of incorrect code.
946
5
        SR.setBegin(DependentTL.getTemplateKeywordLoc());
947
5
      }
948
166
    }
949
950
271
    return SR;
951
271
  }
952
953
271
  syntax::NodeKind getNameSpecifierKind(const NestedNameSpecifier &NNS) {
954
271
    switch (NNS.getKind()) {
955
60
    case NestedNameSpecifier::Global:
956
60
      return syntax::NodeKind::GlobalNameSpecifier;
957
40
    case NestedNameSpecifier::Namespace:
958
40
    case NestedNameSpecifier::NamespaceAlias:
959
45
    case NestedNameSpecifier::Identifier:
960
45
      return syntax::NodeKind::IdentifierNameSpecifier;
961
35
    case NestedNameSpecifier::TypeSpecWithTemplate:
962
35
      return syntax::NodeKind::SimpleTemplateNameSpecifier;
963
131
    case NestedNameSpecifier::TypeSpec: {
964
131
      const auto *NNSType = NNS.getAsType();
965
131
      assert(NNSType);
966
131
      if (isa<DecltypeType>(NNSType))
967
8
        return syntax::NodeKind::DecltypeNameSpecifier;
968
123
      if (isa<TemplateSpecializationType, DependentTemplateSpecializationType>(
969
123
              NNSType))
970
20
        return syntax::NodeKind::SimpleTemplateNameSpecifier;
971
103
      return syntax::NodeKind::IdentifierNameSpecifier;
972
123
    }
973
0
    default:
974
      // FIXME: Support Microsoft's __super
975
0
      llvm::report_fatal_error("We don't yet support the __super specifier",
976
0
                               true);
977
271
    }
978
271
  }
979
980
  syntax::NameSpecifier *
981
271
  buildNameSpecifier(const NestedNameSpecifierLoc &NNSLoc) {
982
271
    assert(NNSLoc.hasQualifier());
983
0
    auto NameSpecifierTokens =
984
271
        Builder.getRange(getLocalSourceRange(NNSLoc)).drop_back();
985
271
    switch (getNameSpecifierKind(*NNSLoc.getNestedNameSpecifier())) {
986
60
    case syntax::NodeKind::GlobalNameSpecifier:
987
60
      return new (allocator()) syntax::GlobalNameSpecifier;
988
148
    case syntax::NodeKind::IdentifierNameSpecifier: {
989
148
      assert(NameSpecifierTokens.size() == 1);
990
0
      Builder.markChildToken(NameSpecifierTokens.begin(),
991
148
                             syntax::NodeRole::Unknown);
992
148
      auto *NS = new (allocator()) syntax::IdentifierNameSpecifier;
993
148
      Builder.foldNode(NameSpecifierTokens, NS, nullptr);
994
148
      return NS;
995
0
    }
996
55
    case syntax::NodeKind::SimpleTemplateNameSpecifier: {
997
      // TODO: Build `SimpleTemplateNameSpecifier` children and implement
998
      // accessors to them.
999
      // Be aware, we cannot do that simply by calling `TraverseTypeLoc`,
1000
      // some `TypeLoc`s have inside them the previous name specifier and
1001
      // we want to treat them independently.
1002
55
      auto *NS = new (allocator()) syntax::SimpleTemplateNameSpecifier;
1003
55
      Builder.foldNode(NameSpecifierTokens, NS, nullptr);
1004
55
      return NS;
1005
0
    }
1006
8
    case syntax::NodeKind::DecltypeNameSpecifier: {
1007
8
      const auto TL = NNSLoc.getTypeLoc().castAs<DecltypeTypeLoc>();
1008
8
      if (!RecursiveASTVisitor::TraverseDecltypeTypeLoc(TL))
1009
0
        return nullptr;
1010
8
      auto *NS = new (allocator()) syntax::DecltypeNameSpecifier;
1011
      // TODO: Implement accessor to `DecltypeNameSpecifier` inner
1012
      // `DecltypeTypeLoc`.
1013
      // For that add mapping from `TypeLoc` to `syntax::Node*` then:
1014
      // Builder.markChild(TypeLoc, syntax::NodeRole);
1015
8
      Builder.foldNode(NameSpecifierTokens, NS, nullptr);
1016
8
      return NS;
1017
8
    }
1018
0
    default:
1019
0
      llvm_unreachable("getChildKind() does not return this value");
1020
271
    }
1021
271
  }
1022
1023
  // To build syntax tree nodes for NestedNameSpecifierLoc we override
1024
  // Traverse instead of WalkUpFrom because we want to traverse the children
1025
  // ourselves and build a list instead of a nested tree of name specifier
1026
  // prefixes.
1027
6.78k
  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc QualifierLoc) {
1028
6.78k
    if (!QualifierLoc)
1029
6.58k
      return true;
1030
472
    
for (auto It = QualifierLoc; 201
It;
It = It.getPrefix()271
) {
1031
271
      auto *NS = buildNameSpecifier(It);
1032
271
      if (!NS)
1033
0
        return false;
1034
271
      Builder.markChild(NS, syntax::NodeRole::ListElement);
1035
271
      Builder.markChildToken(It.getEndLoc(), syntax::NodeRole::ListDelimiter);
1036
271
    }
1037
201
    Builder.foldNode(Builder.getRange(QualifierLoc.getSourceRange()),
1038
201
                     new (allocator()) syntax::NestedNameSpecifier,
1039
201
                     QualifierLoc);
1040
201
    return true;
1041
201
  }
1042
1043
  syntax::IdExpression *buildIdExpression(NestedNameSpecifierLoc QualifierLoc,
1044
                                          SourceLocation TemplateKeywordLoc,
1045
                                          SourceRange UnqualifiedIdLoc,
1046
1.25k
                                          ASTPtr From) {
1047
1.25k
    if (QualifierLoc) {
1048
103
      Builder.markChild(QualifierLoc, syntax::NodeRole::Qualifier);
1049
103
      if (TemplateKeywordLoc.isValid())
1050
35
        Builder.markChildToken(TemplateKeywordLoc,
1051
35
                               syntax::NodeRole::TemplateKeyword);
1052
103
    }
1053
1054
1.25k
    auto *TheUnqualifiedId = new (allocator()) syntax::UnqualifiedId;
1055
1.25k
    Builder.foldNode(Builder.getRange(UnqualifiedIdLoc), TheUnqualifiedId,
1056
1.25k
                     nullptr);
1057
1.25k
    Builder.markChild(TheUnqualifiedId, syntax::NodeRole::UnqualifiedId);
1058
1059
1.25k
    auto IdExpressionBeginLoc =
1060
1.25k
        QualifierLoc ? 
QualifierLoc.getBeginLoc()103
:
UnqualifiedIdLoc.getBegin()1.15k
;
1061
1062
1.25k
    auto *TheIdExpression = new (allocator()) syntax::IdExpression;
1063
1.25k
    Builder.foldNode(
1064
1.25k
        Builder.getRange(IdExpressionBeginLoc, UnqualifiedIdLoc.getEnd()),
1065
1.25k
        TheIdExpression, From);
1066
1067
1.25k
    return TheIdExpression;
1068
1.25k
  }
1069
1070
230
  bool WalkUpFromMemberExpr(MemberExpr *S) {
1071
    // For `MemberExpr` with implicit `this->` we generate a simple
1072
    // `id-expression` syntax node, beacuse an implicit `member-expression` is
1073
    // syntactically undistinguishable from an `id-expression`
1074
230
    if (S->isImplicitAccess()) {
1075
20
      buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),
1076
20
                        SourceRange(S->getMemberLoc(), S->getEndLoc()), S);
1077
20
      return true;
1078
20
    }
1079
1080
210
    auto *TheIdExpression = buildIdExpression(
1081
210
        S->getQualifierLoc(), S->getTemplateKeywordLoc(),
1082
210
        SourceRange(S->getMemberLoc(), S->getEndLoc()), nullptr);
1083
1084
210
    Builder.markChild(TheIdExpression, syntax::NodeRole::Member);
1085
1086
210
    Builder.markExprChild(S->getBase(), syntax::NodeRole::Object);
1087
210
    Builder.markChildToken(S->getOperatorLoc(), syntax::NodeRole::AccessToken);
1088
1089
210
    Builder.foldNode(Builder.getExprRange(S),
1090
210
                     new (allocator()) syntax::MemberExpression, S);
1091
210
    return true;
1092
230
  }
1093
1094
1.00k
  bool WalkUpFromDeclRefExpr(DeclRefExpr *S) {
1095
1.00k
    buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),
1096
1.00k
                      SourceRange(S->getLocation(), S->getEndLoc()), S);
1097
1098
1.00k
    return true;
1099
1.00k
  }
1100
1101
  // Same logic as DeclRefExpr.
1102
15
  bool WalkUpFromDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *S) {
1103
15
    buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),
1104
15
                      SourceRange(S->getLocation(), S->getEndLoc()), S);
1105
1106
15
    return true;
1107
15
  }
1108
1109
60
  bool WalkUpFromCXXThisExpr(CXXThisExpr *S) {
1110
60
    if (!S->isImplicit()) {
1111
40
      Builder.markChildToken(S->getLocation(),
1112
40
                             syntax::NodeRole::IntroducerKeyword);
1113
40
      Builder.foldNode(Builder.getExprRange(S),
1114
40
                       new (allocator()) syntax::ThisExpression, S);
1115
40
    }
1116
60
    return true;
1117
60
  }
1118
1119
118
  bool WalkUpFromParenExpr(ParenExpr *S) {
1120
118
    Builder.markChildToken(S->getLParen(), syntax::NodeRole::OpenParen);
1121
118
    Builder.markExprChild(S->getSubExpr(), syntax::NodeRole::SubExpression);
1122
118
    Builder.markChildToken(S->getRParen(), syntax::NodeRole::CloseParen);
1123
118
    Builder.foldNode(Builder.getExprRange(S),
1124
118
                     new (allocator()) syntax::ParenExpression, S);
1125
118
    return true;
1126
118
  }
1127
1128
1.32k
  bool WalkUpFromIntegerLiteral(IntegerLiteral *S) {
1129
1.32k
    Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1130
1.32k
    Builder.foldNode(Builder.getExprRange(S),
1131
1.32k
                     new (allocator()) syntax::IntegerLiteralExpression, S);
1132
1.32k
    return true;
1133
1.32k
  }
1134
1135
198
  bool WalkUpFromCharacterLiteral(CharacterLiteral *S) {
1136
198
    Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1137
198
    Builder.foldNode(Builder.getExprRange(S),
1138
198
                     new (allocator()) syntax::CharacterLiteralExpression, S);
1139
198
    return true;
1140
198
  }
1141
1142
128
  bool WalkUpFromFloatingLiteral(FloatingLiteral *S) {
1143
128
    Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1144
128
    Builder.foldNode(Builder.getExprRange(S),
1145
128
                     new (allocator()) syntax::FloatingLiteralExpression, S);
1146
128
    return true;
1147
128
  }
1148
1149
68
  bool WalkUpFromStringLiteral(StringLiteral *S) {
1150
68
    Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);
1151
68
    Builder.foldNode(Builder.getExprRange(S),
1152
68
                     new (allocator()) syntax::StringLiteralExpression, S);
1153
68
    return true;
1154
68
  }
1155
1156
80
  bool WalkUpFromCXXBoolLiteralExpr(CXXBoolLiteralExpr *S) {
1157
80
    Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1158
80
    Builder.foldNode(Builder.getExprRange(S),
1159
80
                     new (allocator()) syntax::BoolLiteralExpression, S);
1160
80
    return true;
1161
80
  }
1162
1163
8
  bool WalkUpFromCXXNullPtrLiteralExpr(CXXNullPtrLiteralExpr *S) {
1164
8
    Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1165
8
    Builder.foldNode(Builder.getExprRange(S),
1166
8
                     new (allocator()) syntax::CxxNullPtrExpression, S);
1167
8
    return true;
1168
8
  }
1169
1170
222
  bool WalkUpFromUnaryOperator(UnaryOperator *S) {
1171
222
    Builder.markChildToken(S->getOperatorLoc(),
1172
222
                           syntax::NodeRole::OperatorToken);
1173
222
    Builder.markExprChild(S->getSubExpr(), syntax::NodeRole::Operand);
1174
1175
222
    if (S->isPostfix())
1176
28
      Builder.foldNode(Builder.getExprRange(S),
1177
28
                       new (allocator()) syntax::PostfixUnaryOperatorExpression,
1178
28
                       S);
1179
194
    else
1180
194
      Builder.foldNode(Builder.getExprRange(S),
1181
194
                       new (allocator()) syntax::PrefixUnaryOperatorExpression,
1182
194
                       S);
1183
1184
222
    return true;
1185
222
  }
1186
1187
448
  bool WalkUpFromBinaryOperator(BinaryOperator *S) {
1188
448
    Builder.markExprChild(S->getLHS(), syntax::NodeRole::LeftHandSide);
1189
448
    Builder.markChildToken(S->getOperatorLoc(),
1190
448
                           syntax::NodeRole::OperatorToken);
1191
448
    Builder.markExprChild(S->getRHS(), syntax::NodeRole::RightHandSide);
1192
448
    Builder.foldNode(Builder.getExprRange(S),
1193
448
                     new (allocator()) syntax::BinaryOperatorExpression, S);
1194
448
    return true;
1195
448
  }
1196
1197
  /// Builds `CallArguments` syntax node from arguments that appear in source
1198
  /// code, i.e. not default arguments.
1199
  syntax::CallArguments *
1200
465
  buildCallArguments(CallExpr::arg_range ArgsAndDefaultArgs) {
1201
465
    auto Args = dropDefaultArgs(ArgsAndDefaultArgs);
1202
465
    for (auto *Arg : Args) {
1203
182
      Builder.markExprChild(Arg, syntax::NodeRole::ListElement);
1204
182
      const auto *DelimiterToken =
1205
182
          std::next(Builder.findToken(Arg->getEndLoc()));
1206
182
      if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1207
52
        Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1208
182
    }
1209
1210
465
    auto *Arguments = new (allocator()) syntax::CallArguments;
1211
465
    if (!Args.empty())
1212
130
      Builder.foldNode(Builder.getRange((*Args.begin())->getBeginLoc(),
1213
130
                                        (*(Args.end() - 1))->getEndLoc()),
1214
130
                       Arguments, nullptr);
1215
1216
465
    return Arguments;
1217
465
  }
1218
1219
435
  bool WalkUpFromCallExpr(CallExpr *S) {
1220
435
    Builder.markExprChild(S->getCallee(), syntax::NodeRole::Callee);
1221
1222
435
    const auto *LParenToken =
1223
435
        std::next(Builder.findToken(S->getCallee()->getEndLoc()));
1224
    // FIXME: Assert that `LParenToken` is indeed a `l_paren` once we have fixed
1225
    // the test on decltype desctructors.
1226
435
    if (LParenToken->kind() == clang::tok::l_paren)
1227
427
      Builder.markChildToken(LParenToken, syntax::NodeRole::OpenParen);
1228
1229
435
    Builder.markChild(buildCallArguments(S->arguments()),
1230
435
                      syntax::NodeRole::Arguments);
1231
1232
435
    Builder.markChildToken(S->getRParenLoc(), syntax::NodeRole::CloseParen);
1233
1234
435
    Builder.foldNode(Builder.getRange(S->getSourceRange()),
1235
435
                     new (allocator()) syntax::CallExpression, S);
1236
435
    return true;
1237
435
  }
1238
1239
188
  bool WalkUpFromCXXConstructExpr(CXXConstructExpr *S) {
1240
    // Ignore the implicit calls to default constructors.
1241
188
    if ((S->getNumArgs() == 0 || 
isa<CXXDefaultArgExpr>(S->getArg(0))122
) &&
1242
188
        
S->getParenOrBraceRange().isInvalid()76
)
1243
40
      return true;
1244
148
    return RecursiveASTVisitor::WalkUpFromCXXConstructExpr(S);
1245
188
  }
1246
1247
120
  bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *S) {
1248
    // To construct a syntax tree of the same shape for calls to built-in and
1249
    // user-defined operators, ignore the `DeclRefExpr` that refers to the
1250
    // operator and treat it as a simple token. Do that by traversing
1251
    // arguments instead of children.
1252
180
    for (auto *child : S->arguments()) {
1253
      // A postfix unary operator is declared as taking two operands. The
1254
      // second operand is used to distinguish from its prefix counterpart. In
1255
      // the semantic AST this "phantom" operand is represented as a
1256
      // `IntegerLiteral` with invalid `SourceLocation`. We skip visiting this
1257
      // operand because it does not correspond to anything written in source
1258
      // code.
1259
180
      if (child->getSourceRange().isInvalid()) {
1260
10
        assert(getOperatorNodeKind(*S) ==
1261
10
               syntax::NodeKind::PostfixUnaryOperatorExpression);
1262
0
        continue;
1263
10
      }
1264
170
      if (!TraverseStmt(child))
1265
0
        return false;
1266
170
    }
1267
120
    return WalkUpFromCXXOperatorCallExpr(S);
1268
120
  }
1269
1270
120
  bool WalkUpFromCXXOperatorCallExpr(CXXOperatorCallExpr *S) {
1271
120
    switch (getOperatorNodeKind(*S)) {
1272
50
    case syntax::NodeKind::BinaryOperatorExpression:
1273
50
      Builder.markExprChild(S->getArg(0), syntax::NodeRole::LeftHandSide);
1274
50
      Builder.markChildToken(S->getOperatorLoc(),
1275
50
                             syntax::NodeRole::OperatorToken);
1276
50
      Builder.markExprChild(S->getArg(1), syntax::NodeRole::RightHandSide);
1277
50
      Builder.foldNode(Builder.getExprRange(S),
1278
50
                       new (allocator()) syntax::BinaryOperatorExpression, S);
1279
50
      return true;
1280
30
    case syntax::NodeKind::PrefixUnaryOperatorExpression:
1281
30
      Builder.markChildToken(S->getOperatorLoc(),
1282
30
                             syntax::NodeRole::OperatorToken);
1283
30
      Builder.markExprChild(S->getArg(0), syntax::NodeRole::Operand);
1284
30
      Builder.foldNode(Builder.getExprRange(S),
1285
30
                       new (allocator()) syntax::PrefixUnaryOperatorExpression,
1286
30
                       S);
1287
30
      return true;
1288
10
    case syntax::NodeKind::PostfixUnaryOperatorExpression:
1289
10
      Builder.markChildToken(S->getOperatorLoc(),
1290
10
                             syntax::NodeRole::OperatorToken);
1291
10
      Builder.markExprChild(S->getArg(0), syntax::NodeRole::Operand);
1292
10
      Builder.foldNode(Builder.getExprRange(S),
1293
10
                       new (allocator()) syntax::PostfixUnaryOperatorExpression,
1294
10
                       S);
1295
10
      return true;
1296
30
    case syntax::NodeKind::CallExpression: {
1297
30
      Builder.markExprChild(S->getArg(0), syntax::NodeRole::Callee);
1298
1299
30
      const auto *LParenToken =
1300
30
          std::next(Builder.findToken(S->getArg(0)->getEndLoc()));
1301
      // FIXME: Assert that `LParenToken` is indeed a `l_paren` once we have
1302
      // fixed the test on decltype desctructors.
1303
30
      if (LParenToken->kind() == clang::tok::l_paren)
1304
30
        Builder.markChildToken(LParenToken, syntax::NodeRole::OpenParen);
1305
1306
30
      Builder.markChild(buildCallArguments(CallExpr::arg_range(
1307
30
                            S->arg_begin() + 1, S->arg_end())),
1308
30
                        syntax::NodeRole::Arguments);
1309
1310
30
      Builder.markChildToken(S->getRParenLoc(), syntax::NodeRole::CloseParen);
1311
1312
30
      Builder.foldNode(Builder.getRange(S->getSourceRange()),
1313
30
                       new (allocator()) syntax::CallExpression, S);
1314
30
      return true;
1315
0
    }
1316
0
    case syntax::NodeKind::UnknownExpression:
1317
0
      return WalkUpFromExpr(S);
1318
0
    default:
1319
0
      llvm_unreachable("getOperatorNodeKind() does not return this value");
1320
120
    }
1321
120
  }
1322
1323
74
  bool WalkUpFromCXXDefaultArgExpr(CXXDefaultArgExpr *S) { return true; }
1324
1325
98
  bool WalkUpFromNamespaceDecl(NamespaceDecl *S) {
1326
98
    auto Tokens = Builder.getDeclarationRange(S);
1327
98
    if (Tokens.front().kind() == tok::coloncolon) {
1328
      // Handle nested namespace definitions. Those start at '::' token, e.g.
1329
      // namespace a^::b {}
1330
      // FIXME: build corresponding nodes for the name of this namespace.
1331
4
      return true;
1332
4
    }
1333
94
    Builder.foldNode(Tokens, new (allocator()) syntax::NamespaceDefinition, S);
1334
94
    return true;
1335
98
  }
1336
1337
  // FIXME: Deleting the `TraverseParenTypeLoc` override doesn't change test
1338
  // results. Find test coverage or remove it.
1339
156
  bool TraverseParenTypeLoc(ParenTypeLoc L) {
1340
    // We reverse order of traversal to get the proper syntax structure.
1341
156
    if (!WalkUpFromParenTypeLoc(L))
1342
0
      return false;
1343
156
    return TraverseTypeLoc(L.getInnerLoc());
1344
156
  }
1345
1346
156
  bool WalkUpFromParenTypeLoc(ParenTypeLoc L) {
1347
156
    Builder.markChildToken(L.getLParenLoc(), syntax::NodeRole::OpenParen);
1348
156
    Builder.markChildToken(L.getRParenLoc(), syntax::NodeRole::CloseParen);
1349
156
    Builder.foldNode(Builder.getRange(L.getLParenLoc(), L.getRParenLoc()),
1350
156
                     new (allocator()) syntax::ParenDeclarator, L);
1351
156
    return true;
1352
156
  }
1353
1354
  // Declarator chunks, they are produced by type locs and some clang::Decls.
1355
88
  bool WalkUpFromArrayTypeLoc(ArrayTypeLoc L) {
1356
88
    Builder.markChildToken(L.getLBracketLoc(), syntax::NodeRole::OpenParen);
1357
88
    Builder.markExprChild(L.getSizeExpr(), syntax::NodeRole::Size);
1358
88
    Builder.markChildToken(L.getRBracketLoc(), syntax::NodeRole::CloseParen);
1359
88
    Builder.foldNode(Builder.getRange(L.getLBracketLoc(), L.getRBracketLoc()),
1360
88
                     new (allocator()) syntax::ArraySubscript, L);
1361
88
    return true;
1362
88
  }
1363
1364
  syntax::ParameterDeclarationList *
1365
2.33k
  buildParameterDeclarationList(ArrayRef<ParmVarDecl *> Params) {
1366
2.33k
    for (auto *P : Params) {
1367
1.49k
      Builder.markChild(P, syntax::NodeRole::ListElement);
1368
1.49k
      const auto *DelimiterToken = std::next(Builder.findToken(P->getEndLoc()));
1369
1.49k
      if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1370
408
        Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1371
1.49k
    }
1372
2.33k
    auto *Parameters = new (allocator()) syntax::ParameterDeclarationList;
1373
2.33k
    if (!Params.empty())
1374
1.08k
      Builder.foldNode(Builder.getRange(Params.front()->getBeginLoc(),
1375
1.08k
                                        Params.back()->getEndLoc()),
1376
1.08k
                       Parameters, nullptr);
1377
2.33k
    return Parameters;
1378
2.33k
  }
1379
1380
2.33k
  bool WalkUpFromFunctionTypeLoc(FunctionTypeLoc L) {
1381
2.33k
    Builder.markChildToken(L.getLParenLoc(), syntax::NodeRole::OpenParen);
1382
1383
2.33k
    Builder.markChild(buildParameterDeclarationList(L.getParams()),
1384
2.33k
                      syntax::NodeRole::Parameters);
1385
1386
2.33k
    Builder.markChildToken(L.getRParenLoc(), syntax::NodeRole::CloseParen);
1387
2.33k
    Builder.foldNode(Builder.getRange(L.getLParenLoc(), L.getEndLoc()),
1388
2.33k
                     new (allocator()) syntax::ParametersAndQualifiers, L);
1389
2.33k
    return true;
1390
2.33k
  }
1391
1392
2.22k
  bool WalkUpFromFunctionProtoTypeLoc(FunctionProtoTypeLoc L) {
1393
2.22k
    if (!L.getTypePtr()->hasTrailingReturn())
1394
2.20k
      return WalkUpFromFunctionTypeLoc(L);
1395
1396
24
    auto *TrailingReturnTokens = buildTrailingReturn(L);
1397
    // Finish building the node for parameters.
1398
24
    Builder.markChild(TrailingReturnTokens, syntax::NodeRole::TrailingReturn);
1399
24
    return WalkUpFromFunctionTypeLoc(L);
1400
2.22k
  }
1401
1402
70
  bool TraverseMemberPointerTypeLoc(MemberPointerTypeLoc L) {
1403
    // In the source code "void (Y::*mp)()" `MemberPointerTypeLoc` corresponds
1404
    // to "Y::*" but it points to a `ParenTypeLoc` that corresponds to
1405
    // "(Y::*mp)" We thus reverse the order of traversal to get the proper
1406
    // syntax structure.
1407
70
    if (!WalkUpFromMemberPointerTypeLoc(L))
1408
0
      return false;
1409
70
    return TraverseTypeLoc(L.getPointeeLoc());
1410
70
  }
1411
1412
70
  bool WalkUpFromMemberPointerTypeLoc(MemberPointerTypeLoc L) {
1413
70
    auto SR = L.getLocalSourceRange();
1414
70
    Builder.foldNode(Builder.getRange(SR),
1415
70
                     new (allocator()) syntax::MemberPointer, L);
1416
70
    return true;
1417
70
  }
1418
1419
  // The code below is very regular, it could even be generated with some
1420
  // preprocessor magic. We merely assign roles to the corresponding children
1421
  // and fold resulting nodes.
1422
196
  bool WalkUpFromDeclStmt(DeclStmt *S) {
1423
196
    Builder.foldNode(Builder.getStmtRange(S),
1424
196
                     new (allocator()) syntax::DeclarationStatement, S);
1425
196
    return true;
1426
196
  }
1427
1428
36
  bool WalkUpFromNullStmt(NullStmt *S) {
1429
36
    Builder.foldNode(Builder.getStmtRange(S),
1430
36
                     new (allocator()) syntax::EmptyStatement, S);
1431
36
    return true;
1432
36
  }
1433
1434
14
  bool WalkUpFromSwitchStmt(SwitchStmt *S) {
1435
14
    Builder.markChildToken(S->getSwitchLoc(),
1436
14
                           syntax::NodeRole::IntroducerKeyword);
1437
14
    Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
1438
14
    Builder.foldNode(Builder.getStmtRange(S),
1439
14
                     new (allocator()) syntax::SwitchStatement, S);
1440
14
    return true;
1441
14
  }
1442
1443
14
  bool WalkUpFromCaseStmt(CaseStmt *S) {
1444
14
    Builder.markChildToken(S->getKeywordLoc(),
1445
14
                           syntax::NodeRole::IntroducerKeyword);
1446
14
    Builder.markExprChild(S->getLHS(), syntax::NodeRole::CaseValue);
1447
14
    Builder.markStmtChild(S->getSubStmt(), syntax::NodeRole::BodyStatement);
1448
14
    Builder.foldNode(Builder.getStmtRange(S),
1449
14
                     new (allocator()) syntax::CaseStatement, S);
1450
14
    return true;
1451
14
  }
1452
1453
14
  bool WalkUpFromDefaultStmt(DefaultStmt *S) {
1454
14
    Builder.markChildToken(S->getKeywordLoc(),
1455
14
                           syntax::NodeRole::IntroducerKeyword);
1456
14
    Builder.markStmtChild(S->getSubStmt(), syntax::NodeRole::BodyStatement);
1457
14
    Builder.foldNode(Builder.getStmtRange(S),
1458
14
                     new (allocator()) syntax::DefaultStatement, S);
1459
14
    return true;
1460
14
  }
1461
1462
120
  bool WalkUpFromIfStmt(IfStmt *S) {
1463
120
    Builder.markChildToken(S->getIfLoc(), syntax::NodeRole::IntroducerKeyword);
1464
120
    Stmt *ConditionStatement = S->getCond();
1465
120
    if (S->hasVarStorage())
1466
4
      ConditionStatement = S->getConditionVariableDeclStmt();
1467
120
    Builder.markStmtChild(ConditionStatement, syntax::NodeRole::Condition);
1468
120
    Builder.markStmtChild(S->getThen(), syntax::NodeRole::ThenStatement);
1469
120
    Builder.markChildToken(S->getElseLoc(), syntax::NodeRole::ElseKeyword);
1470
120
    Builder.markStmtChild(S->getElse(), syntax::NodeRole::ElseStatement);
1471
120
    Builder.foldNode(Builder.getStmtRange(S),
1472
120
                     new (allocator()) syntax::IfStatement, S);
1473
120
    return true;
1474
120
  }
1475
1476
14
  bool WalkUpFromForStmt(ForStmt *S) {
1477
14
    Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);
1478
14
    Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
1479
14
    Builder.foldNode(Builder.getStmtRange(S),
1480
14
                     new (allocator()) syntax::ForStatement, S);
1481
14
    return true;
1482
14
  }
1483
1484
14
  bool WalkUpFromWhileStmt(WhileStmt *S) {
1485
14
    Builder.markChildToken(S->getWhileLoc(),
1486
14
                           syntax::NodeRole::IntroducerKeyword);
1487
14
    Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
1488
14
    Builder.foldNode(Builder.getStmtRange(S),
1489
14
                     new (allocator()) syntax::WhileStatement, S);
1490
14
    return true;
1491
14
  }
1492
1493
14
  bool WalkUpFromContinueStmt(ContinueStmt *S) {
1494
14
    Builder.markChildToken(S->getContinueLoc(),
1495
14
                           syntax::NodeRole::IntroducerKeyword);
1496
14
    Builder.foldNode(Builder.getStmtRange(S),
1497
14
                     new (allocator()) syntax::ContinueStatement, S);
1498
14
    return true;
1499
14
  }
1500
1501
14
  bool WalkUpFromBreakStmt(BreakStmt *S) {
1502
14
    Builder.markChildToken(S->getBreakLoc(),
1503
14
                           syntax::NodeRole::IntroducerKeyword);
1504
14
    Builder.foldNode(Builder.getStmtRange(S),
1505
14
                     new (allocator()) syntax::BreakStatement, S);
1506
14
    return true;
1507
14
  }
1508
1509
74
  bool WalkUpFromReturnStmt(ReturnStmt *S) {
1510
74
    Builder.markChildToken(S->getReturnLoc(),
1511
74
                           syntax::NodeRole::IntroducerKeyword);
1512
74
    Builder.markExprChild(S->getRetValue(), syntax::NodeRole::ReturnValue);
1513
74
    Builder.foldNode(Builder.getStmtRange(S),
1514
74
                     new (allocator()) syntax::ReturnStatement, S);
1515
74
    return true;
1516
74
  }
1517
1518
8
  bool WalkUpFromCXXForRangeStmt(CXXForRangeStmt *S) {
1519
8
    Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);
1520
8
    Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
1521
8
    Builder.foldNode(Builder.getStmtRange(S),
1522
8
                     new (allocator()) syntax::RangeBasedForStatement, S);
1523
8
    return true;
1524
8
  }
1525
1526
14
  bool WalkUpFromEmptyDecl(EmptyDecl *S) {
1527
14
    Builder.foldNode(Builder.getDeclarationRange(S),
1528
14
                     new (allocator()) syntax::EmptyDeclaration, S);
1529
14
    return true;
1530
14
  }
1531
1532
12
  bool WalkUpFromStaticAssertDecl(StaticAssertDecl *S) {
1533
12
    Builder.markExprChild(S->getAssertExpr(), syntax::NodeRole::Condition);
1534
12
    Builder.markExprChild(S->getMessage(), syntax::NodeRole::Message);
1535
12
    Builder.foldNode(Builder.getDeclarationRange(S),
1536
12
                     new (allocator()) syntax::StaticAssertDeclaration, S);
1537
12
    return true;
1538
12
  }
1539
1540
20
  bool WalkUpFromLinkageSpecDecl(LinkageSpecDecl *S) {
1541
20
    Builder.foldNode(Builder.getDeclarationRange(S),
1542
20
                     new (allocator()) syntax::LinkageSpecificationDeclaration,
1543
20
                     S);
1544
20
    return true;
1545
20
  }
1546
1547
10
  bool WalkUpFromNamespaceAliasDecl(NamespaceAliasDecl *S) {
1548
10
    Builder.foldNode(Builder.getDeclarationRange(S),
1549
10
                     new (allocator()) syntax::NamespaceAliasDefinition, S);
1550
10
    return true;
1551
10
  }
1552
1553
10
  bool WalkUpFromUsingDirectiveDecl(UsingDirectiveDecl *S) {
1554
10
    Builder.foldNode(Builder.getDeclarationRange(S),
1555
10
                     new (allocator()) syntax::UsingNamespaceDirective, S);
1556
10
    return true;
1557
10
  }
1558
1559
10
  bool WalkUpFromUsingDecl(UsingDecl *S) {
1560
10
    Builder.foldNode(Builder.getDeclarationRange(S),
1561
10
                     new (allocator()) syntax::UsingDeclaration, S);
1562
10
    return true;
1563
10
  }
1564
1565
10
  bool WalkUpFromUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *S) {
1566
10
    Builder.foldNode(Builder.getDeclarationRange(S),
1567
10
                     new (allocator()) syntax::UsingDeclaration, S);
1568
10
    return true;
1569
10
  }
1570
1571
10
  bool WalkUpFromUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *S) {
1572
10
    Builder.foldNode(Builder.getDeclarationRange(S),
1573
10
                     new (allocator()) syntax::UsingDeclaration, S);
1574
10
    return true;
1575
10
  }
1576
1577
8
  bool WalkUpFromTypeAliasDecl(TypeAliasDecl *S) {
1578
8
    Builder.foldNode(Builder.getDeclarationRange(S),
1579
8
                     new (allocator()) syntax::TypeAliasDeclaration, S);
1580
8
    return true;
1581
8
  }
1582
1583
private:
1584
  /// Folds SimpleDeclarator node (if present) and in case this is the last
1585
  /// declarator in the chain it also folds SimpleDeclaration node.
1586
4.59k
  template <class T> bool processDeclaratorAndDeclaration(T *D) {
1587
4.59k
    auto Range = getDeclaratorRange(
1588
4.59k
        Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
1589
4.59k
        getQualifiedNameStart(D), getInitializerRange(D));
1590
1591
    // There doesn't have to be a declarator (e.g. `void foo(int)` only has
1592
    // declaration, but no declarator).
1593
4.59k
    if (!Range.getBegin().isValid()) {
1594
530
      Builder.markChild(new (allocator()) syntax::DeclaratorList,
1595
530
                        syntax::NodeRole::Declarators);
1596
530
      Builder.foldNode(Builder.getDeclarationRange(D),
1597
530
                       new (allocator()) syntax::SimpleDeclaration, D);
1598
530
      return true;
1599
530
    }
1600
1601
4.06k
    auto *N = new (allocator()) syntax::SimpleDeclarator;
1602
4.06k
    Builder.foldNode(Builder.getRange(Range), N, nullptr);
1603
4.06k
    Builder.markChild(N, syntax::NodeRole::ListElement);
1604
1605
4.06k
    if (!Builder.isResponsibleForCreatingDeclaration(D)) {
1606
      // If this is not the last declarator in the declaration we expect a
1607
      // delimiter after it.
1608
70
      const auto *DelimiterToken = std::next(Builder.findToken(Range.getEnd()));
1609
70
      if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1610
70
        Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1611
3.99k
    } else {
1612
3.99k
      auto *DL = new (allocator()) syntax::DeclaratorList;
1613
3.99k
      auto DeclarationRange = Builder.getDeclarationRange(D);
1614
3.99k
      Builder.foldList(DeclarationRange, DL, nullptr);
1615
1616
3.99k
      Builder.markChild(DL, syntax::NodeRole::Declarators);
1617
3.99k
      Builder.foldNode(DeclarationRange,
1618
3.99k
                       new (allocator()) syntax::SimpleDeclaration, D);
1619
3.99k
    }
1620
4.06k
    return true;
1621
4.59k
  }
BuildTree.cpp:bool (anonymous namespace)::BuildTreeVisitor::processDeclaratorAndDeclaration<clang::TypedefNameDecl>(clang::TypedefNameDecl*)
Line
Count
Source
1586
72
  template <class T> bool processDeclaratorAndDeclaration(T *D) {
1587
72
    auto Range = getDeclaratorRange(
1588
72
        Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
1589
72
        getQualifiedNameStart(D), getInitializerRange(D));
1590
1591
    // There doesn't have to be a declarator (e.g. `void foo(int)` only has
1592
    // declaration, but no declarator).
1593
72
    if (!Range.getBegin().isValid()) {
1594
0
      Builder.markChild(new (allocator()) syntax::DeclaratorList,
1595
0
                        syntax::NodeRole::Declarators);
1596
0
      Builder.foldNode(Builder.getDeclarationRange(D),
1597
0
                       new (allocator()) syntax::SimpleDeclaration, D);
1598
0
      return true;
1599
0
    }
1600
1601
72
    auto *N = new (allocator()) syntax::SimpleDeclarator;
1602
72
    Builder.foldNode(Builder.getRange(Range), N, nullptr);
1603
72
    Builder.markChild(N, syntax::NodeRole::ListElement);
1604
1605
72
    if (!Builder.isResponsibleForCreatingDeclaration(D)) {
1606
      // If this is not the last declarator in the declaration we expect a
1607
      // delimiter after it.
1608
28
      const auto *DelimiterToken = std::next(Builder.findToken(Range.getEnd()));
1609
28
      if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1610
28
        Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1611
44
    } else {
1612
44
      auto *DL = new (allocator()) syntax::DeclaratorList;
1613
44
      auto DeclarationRange = Builder.getDeclarationRange(D);
1614
44
      Builder.foldList(DeclarationRange, DL, nullptr);
1615
1616
44
      Builder.markChild(DL, syntax::NodeRole::Declarators);
1617
44
      Builder.foldNode(DeclarationRange,
1618
44
                       new (allocator()) syntax::SimpleDeclaration, D);
1619
44
    }
1620
72
    return true;
1621
72
  }
BuildTree.cpp:bool (anonymous namespace)::BuildTreeVisitor::processDeclaratorAndDeclaration<clang::DeclaratorDecl>(clang::DeclaratorDecl*)
Line
Count
Source
1586
4.52k
  template <class T> bool processDeclaratorAndDeclaration(T *D) {
1587
4.52k
    auto Range = getDeclaratorRange(
1588
4.52k
        Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
1589
4.52k
        getQualifiedNameStart(D), getInitializerRange(D));
1590
1591
    // There doesn't have to be a declarator (e.g. `void foo(int)` only has
1592
    // declaration, but no declarator).
1593
4.52k
    if (!Range.getBegin().isValid()) {
1594
530
      Builder.markChild(new (allocator()) syntax::DeclaratorList,
1595
530
                        syntax::NodeRole::Declarators);
1596
530
      Builder.foldNode(Builder.getDeclarationRange(D),
1597
530
                       new (allocator()) syntax::SimpleDeclaration, D);
1598
530
      return true;
1599
530
    }
1600
1601
3.99k
    auto *N = new (allocator()) syntax::SimpleDeclarator;
1602
3.99k
    Builder.foldNode(Builder.getRange(Range), N, nullptr);
1603
3.99k
    Builder.markChild(N, syntax::NodeRole::ListElement);
1604
1605
3.99k
    if (!Builder.isResponsibleForCreatingDeclaration(D)) {
1606
      // If this is not the last declarator in the declaration we expect a
1607
      // delimiter after it.
1608
42
      const auto *DelimiterToken = std::next(Builder.findToken(Range.getEnd()));
1609
42
      if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1610
42
        Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1611
3.95k
    } else {
1612
3.95k
      auto *DL = new (allocator()) syntax::DeclaratorList;
1613
3.95k
      auto DeclarationRange = Builder.getDeclarationRange(D);
1614
3.95k
      Builder.foldList(DeclarationRange, DL, nullptr);
1615
1616
3.95k
      Builder.markChild(DL, syntax::NodeRole::Declarators);
1617
3.95k
      Builder.foldNode(DeclarationRange,
1618
3.95k
                       new (allocator()) syntax::SimpleDeclaration, D);
1619
3.95k
    }
1620
3.99k
    return true;
1621
4.52k
  }
1622
1623
  /// Returns the range of the built node.
1624
24
  syntax::TrailingReturnType *buildTrailingReturn(FunctionProtoTypeLoc L) {
1625
24
    assert(L.getTypePtr()->hasTrailingReturn());
1626
1627
0
    auto ReturnedType = L.getReturnLoc();
1628
    // Build node for the declarator, if any.
1629
24
    auto ReturnDeclaratorRange = SourceRange(GetStartLoc().Visit(ReturnedType),
1630
24
                                             ReturnedType.getEndLoc());
1631
24
    syntax::SimpleDeclarator *ReturnDeclarator = nullptr;
1632
24
    if (ReturnDeclaratorRange.isValid()) {
1633
16
      ReturnDeclarator = new (allocator()) syntax::SimpleDeclarator;
1634
16
      Builder.foldNode(Builder.getRange(ReturnDeclaratorRange),
1635
16
                       ReturnDeclarator, nullptr);
1636
16
    }
1637
1638
    // Build node for trailing return type.
1639
24
    auto Return = Builder.getRange(ReturnedType.getSourceRange());
1640
24
    const auto *Arrow = Return.begin() - 1;
1641
24
    assert(Arrow->kind() == tok::arrow);
1642
0
    auto Tokens = llvm::makeArrayRef(Arrow, Return.end());
1643
24
    Builder.markChildToken(Arrow, syntax::NodeRole::ArrowToken);
1644
24
    if (ReturnDeclarator)
1645
16
      Builder.markChild(ReturnDeclarator, syntax::NodeRole::Declarator);
1646
24
    auto *R = new (allocator()) syntax::TrailingReturnType;
1647
24
    Builder.foldNode(Tokens, R, L);
1648
24
    return R;
1649
24
  }
1650
1651
  void foldExplicitTemplateInstantiation(
1652
      ArrayRef<syntax::Token> Range, const syntax::Token *ExternKW,
1653
      const syntax::Token *TemplateKW,
1654
20
      syntax::SimpleDeclaration *InnerDeclaration, Decl *From) {
1655
20
    assert(!ExternKW || ExternKW->kind() == tok::kw_extern);
1656
0
    assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
1657
0
    Builder.markChildToken(ExternKW, syntax::NodeRole::ExternKeyword);
1658
20
    Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);
1659
20
    Builder.markChild(InnerDeclaration, syntax::NodeRole::Declaration);
1660
20
    Builder.foldNode(
1661
20
        Range, new (allocator()) syntax::ExplicitTemplateInstantiation, From);
1662
20
  }
1663
1664
  syntax::TemplateDeclaration *foldTemplateDeclaration(
1665
      ArrayRef<syntax::Token> Range, const syntax::Token *TemplateKW,
1666
303
      ArrayRef<syntax::Token> TemplatedDeclaration, Decl *From) {
1667
303
    assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
1668
0
    Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);
1669
1670
303
    auto *N = new (allocator()) syntax::TemplateDeclaration;
1671
303
    Builder.foldNode(Range, N, From);
1672
303
    Builder.markChild(N, syntax::NodeRole::Declaration);
1673
303
    return N;
1674
303
  }
1675
1676
  /// A small helper to save some typing.
1677
29.0k
  llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }
1678
1679
  syntax::TreeBuilder &Builder;
1680
  const ASTContext &Context;
1681
};
1682
} // namespace
1683
1684
224
void syntax::TreeBuilder::noticeDeclWithoutSemicolon(Decl *D) {
1685
224
  DeclsWithoutSemicolons.insert(D);
1686
224
}
1687
1688
12.3k
void syntax::TreeBuilder::markChildToken(SourceLocation Loc, NodeRole Role) {
1689
12.3k
  if (Loc.isInvalid())
1690
36
    return;
1691
12.2k
  Pending.assignRole(*findToken(Loc), Role);
1692
12.2k
}
1693
1694
1.50k
void syntax::TreeBuilder::markChildToken(const syntax::Token *T, NodeRole R) {
1695
1.50k
  if (!T)
1696
10
    return;
1697
1.49k
  Pending.assignRole(*T, R);
1698
1.49k
}
1699
1700
13.4k
void syntax::TreeBuilder::markChild(syntax::Node *N, NodeRole R) {
1701
13.4k
  assert(N);
1702
0
  setRole(N, R);
1703
13.4k
}
1704
1705
1.49k
void syntax::TreeBuilder::markChild(ASTPtr N, NodeRole R) {
1706
1.49k
  auto *SN = Mapping.find(N);
1707
1.49k
  assert(SN != nullptr);
1708
0
  setRole(SN, R);
1709
1.49k
}
1710
103
void syntax::TreeBuilder::markChild(NestedNameSpecifierLoc NNSLoc, NodeRole R) {
1711
103
  auto *SN = Mapping.find(NNSLoc);
1712
103
  assert(SN != nullptr);
1713
0
  setRole(SN, R);
1714
103
}
1715
1716
2.44k
void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
1717
2.44k
  if (!Child)
1718
36
    return;
1719
1720
2.40k
  syntax::Tree *ChildNode;
1721
2.40k
  if (Expr *ChildExpr = dyn_cast<Expr>(Child)) {
1722
    // This is an expression in a statement position, consume the trailing
1723
    // semicolon and form an 'ExpressionStatement' node.
1724
1.64k
    markExprChild(ChildExpr, NodeRole::Expression);
1725
1.64k
    ChildNode = new (allocator()) syntax::ExpressionStatement;
1726
    // (!) 'getStmtRange()' ensures this covers a trailing semicolon.
1727
1.64k
    Pending.foldChildren(TBTM.tokenBuffer(), getStmtRange(Child), ChildNode);
1728
1.64k
  } else {
1729
760
    ChildNode = Mapping.find(Child);
1730
760
  }
1731
2.40k
  assert(ChildNode != nullptr);
1732
0
  setRole(ChildNode, Role);
1733
2.40k
}
1734
1735
4.08k
void syntax::TreeBuilder::markExprChild(Expr *Child, NodeRole Role) {
1736
4.08k
  if (!Child)
1737
26
    return;
1738
4.05k
  Child = IgnoreImplicit(Child);
1739
1740
4.05k
  syntax::Tree *ChildNode = Mapping.find(Child);
1741
4.05k
  assert(ChildNode != nullptr);
1742
0
  setRole(ChildNode, Role);
1743
4.05k
}
1744
1745
64.6k
const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {
1746
64.6k
  if (L.isInvalid())
1747
10
    return nullptr;
1748
64.5k
  auto It = LocationToToken.find(L);
1749
64.5k
  assert(It != LocationToToken.end());
1750
0
  return It->second;
1751
64.6k
}
1752
1753
syntax::TranslationUnit *syntax::buildSyntaxTree(Arena &A,
1754
                                                 TokenBufferTokenManager& TBTM,
1755
2.16k
                                                 ASTContext &Context) {
1756
2.16k
  TreeBuilder Builder(A, TBTM);
1757
2.16k
  BuildTreeVisitor(Context, Builder).TraverseAST(Context);
1758
2.16k
  return std::move(Builder).finalize();
1759
2.16k
}