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