Coverage Report

Created: 2021-01-23 06:44

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