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