Coverage Report

Created: 2022-01-25 06:29

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