Coverage Report

Created: 2020-09-22 08:39

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