Coverage Report

Created: 2021-09-21 08:58

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