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 // ExplicitInstantiationDecl is an auxiliary AST node that records source
741 // info. The syntax tree is already built by
742 // TraverseClassTemplateSpecializationDecl or by the parser for
743 // function/variable templates, so skip this node.
744 bool TraverseExplicitInstantiationDecl(ExplicitInstantiationDecl *) {
745 return true;
746 }
747
748 bool WalkUpFromTemplateDecl(TemplateDecl *S) {
749 foldTemplateDeclaration(
750 Range: Builder.getDeclarationRange(D: S),
751 TemplateKW: Builder.findToken(L: S->getTemplateParameters()->getTemplateLoc()),
752 TemplatedDeclaration: Builder.getDeclarationRange(D: S->getTemplatedDecl()), From: S);
753 return true;
754 }
755
756 bool WalkUpFromTagDecl(TagDecl *C) {
757 // FIXME: build the ClassSpecifier node.
758 if (!C->isFreeStanding()) {
759 assert(C->getTemplateParameterLists().empty());
760 return true;
761 }
762 handleFreeStandingTagDecl(C);
763 return true;
764 }
765
766 syntax::Declaration *handleFreeStandingTagDecl(TagDecl *C) {
767 assert(C->isFreeStanding());
768 // Class is a declaration specifier and needs a spanning declaration node.
769 auto DeclarationRange = Builder.getDeclarationRange(D: C);
770 syntax::Declaration *Result = new (allocator()) syntax::SimpleDeclaration;
771 Builder.foldNode(Range: DeclarationRange, New: Result, From: nullptr);
772
773 // Build TemplateDeclaration nodes if we had template parameters.
774 auto ConsumeTemplateParameters = [&](const TemplateParameterList &L) {
775 const auto *TemplateKW = Builder.findToken(L: L.getTemplateLoc());
776 auto R = llvm::ArrayRef(TemplateKW, DeclarationRange.end());
777 Result =
778 foldTemplateDeclaration(Range: R, TemplateKW, TemplatedDeclaration: DeclarationRange, From: nullptr);
779 DeclarationRange = R;
780 };
781 if (auto *S = dyn_cast<ClassTemplatePartialSpecializationDecl>(Val: C))
782 ConsumeTemplateParameters(*S->getTemplateParameters());
783 for (TemplateParameterList *TPL : C->getTemplateParameterLists())
784 ConsumeTemplateParameters(*TPL);
785 return Result;
786 }
787
788 bool WalkUpFromTranslationUnitDecl(TranslationUnitDecl *TU) {
789 // We do not want to call VisitDecl(), the declaration for translation
790 // unit is built by finalize().
791 return true;
792 }
793
794 bool WalkUpFromCompoundStmt(CompoundStmt *S) {
795 using NodeRole = syntax::NodeRole;
796
797 Builder.markChildToken(Loc: S->getLBracLoc(), R: NodeRole::OpenParen);
798 for (auto *Child : S->body())
799 Builder.markStmtChild(Child, Role: NodeRole::Statement);
800 Builder.markChildToken(Loc: S->getRBracLoc(), R: NodeRole::CloseParen);
801
802 Builder.foldNode(Range: Builder.getStmtRange(S),
803 New: new (allocator()) syntax::CompoundStatement, From: S);
804 return true;
805 }
806
807 // Some statements are not yet handled by syntax trees.
808 bool WalkUpFromStmt(Stmt *S) {
809 Builder.foldNode(Range: Builder.getStmtRange(S),
810 New: new (allocator()) syntax::UnknownStatement, From: S);
811 return true;
812 }
813
814 bool TraverseIfStmt(IfStmt *S) {
815 bool Result = [&, this]() {
816 if (S->getInit() && !TraverseStmt(S: S->getInit())) {
817 return false;
818 }
819 // In cases where the condition is an initialized declaration in a
820 // statement, we want to preserve the declaration and ignore the
821 // implicit condition expression in the syntax tree.
822 if (S->hasVarStorage()) {
823 if (!TraverseStmt(S: S->getConditionVariableDeclStmt()))
824 return false;
825 } else if (S->getCond() && !TraverseStmt(S: S->getCond()))
826 return false;
827
828 if (S->getThen() && !TraverseStmt(S: S->getThen()))
829 return false;
830 if (S->getElse() && !TraverseStmt(S: S->getElse()))
831 return false;
832 return true;
833 }();
834 WalkUpFromIfStmt(S);
835 return Result;
836 }
837
838 bool TraverseCXXForRangeStmt(CXXForRangeStmt *S) {
839 // We override to traverse range initializer as VarDecl.
840 // RAV traverses it as a statement, we produce invalid node kinds in that
841 // case.
842 // FIXME: should do this in RAV instead?
843 bool Result = [&, this]() {
844 if (S->getInit() && !TraverseStmt(S: S->getInit()))
845 return false;
846 if (S->getLoopVariable() && !TraverseDecl(D: S->getLoopVariable()))
847 return false;
848 if (S->getRangeInit() && !TraverseStmt(S: S->getRangeInit()))
849 return false;
850 if (S->getBody() && !TraverseStmt(S: S->getBody()))
851 return false;
852 return true;
853 }();
854 WalkUpFromCXXForRangeStmt(S);
855 return Result;
856 }
857
858 bool TraverseStmt(Stmt *S) {
859 if (auto *DS = dyn_cast_or_null<DeclStmt>(Val: S)) {
860 // We want to consume the semicolon, make sure SimpleDeclaration does not.
861 for (auto *D : DS->decls())
862 Builder.noticeDeclWithoutSemicolon(D);
863 } else if (auto *E = dyn_cast_or_null<Expr>(Val: S)) {
864 return RecursiveASTVisitor::TraverseStmt(S: IgnoreImplicit(E));
865 }
866 return RecursiveASTVisitor::TraverseStmt(S);
867 }
868
869 bool TraverseOpaqueValueExpr(OpaqueValueExpr *VE) {
870 // OpaqueValue doesn't correspond to concrete syntax, ignore it.
871 return true;
872 }
873
874 // Some expressions are not yet handled by syntax trees.
875 bool WalkUpFromExpr(Expr *E) {
876 assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");
877 Builder.foldNode(Range: Builder.getExprRange(E),
878 New: new (allocator()) syntax::UnknownExpression, From: E);
879 return true;
880 }
881
882 bool TraverseUserDefinedLiteral(UserDefinedLiteral *S) {
883 // The semantic AST node `UserDefinedLiteral` (UDL) may have one child node
884 // referencing the location of the UDL suffix (`_w` in `1.2_w`). The
885 // UDL suffix location does not point to the beginning of a token, so we
886 // can't represent the UDL suffix as a separate syntax tree node.
887
888 return WalkUpFromUserDefinedLiteral(S);
889 }
890
891 syntax::UserDefinedLiteralExpression *
892 buildUserDefinedLiteral(UserDefinedLiteral *S) {
893 switch (S->getLiteralOperatorKind()) {
894 case UserDefinedLiteral::LOK_Integer:
895 return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;
896 case UserDefinedLiteral::LOK_Floating:
897 return new (allocator()) syntax::FloatUserDefinedLiteralExpression;
898 case UserDefinedLiteral::LOK_Character:
899 return new (allocator()) syntax::CharUserDefinedLiteralExpression;
900 case UserDefinedLiteral::LOK_String:
901 return new (allocator()) syntax::StringUserDefinedLiteralExpression;
902 case UserDefinedLiteral::LOK_Raw:
903 case UserDefinedLiteral::LOK_Template:
904 // For raw literal operator and numeric literal operator template we
905 // cannot get the type of the operand in the semantic AST. We get this
906 // information from the token. As integer and floating point have the same
907 // token kind, we run `NumericLiteralParser` again to distinguish them.
908 auto TokLoc = S->getBeginLoc();
909 auto TokSpelling =
910 Builder.findToken(L: TokLoc)->text(SM: Context.getSourceManager());
911 auto Literal =
912 NumericLiteralParser(TokSpelling, TokLoc, Context.getSourceManager(),
913 Context.getLangOpts(), Context.getTargetInfo(),
914 Context.getDiagnostics());
915 if (Literal.isIntegerLiteral())
916 return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;
917 else {
918 assert(Literal.isFloatingLiteral());
919 return new (allocator()) syntax::FloatUserDefinedLiteralExpression;
920 }
921 }
922 llvm_unreachable("Unknown literal operator kind.");
923 }
924
925 bool WalkUpFromUserDefinedLiteral(UserDefinedLiteral *S) {
926 Builder.markChildToken(Loc: S->getBeginLoc(), R: syntax::NodeRole::LiteralToken);
927 Builder.foldNode(Range: Builder.getExprRange(E: S), New: buildUserDefinedLiteral(S), From: S);
928 return true;
929 }
930
931 syntax::NameSpecifier *buildIdentifier(SourceRange SR,
932 bool DropBack = false) {
933 auto NameSpecifierTokens = Builder.getRange(Range: SR).drop_back(N: DropBack);
934 assert(NameSpecifierTokens.size() == 1);
935 Builder.markChildToken(T: NameSpecifierTokens.begin(),
936 R: syntax::NodeRole::Unknown);
937 auto *NS = new (allocator()) syntax::IdentifierNameSpecifier;
938 Builder.foldNode(Range: NameSpecifierTokens, New: NS, From: nullptr);
939 return NS;
940 }
941
942 syntax::NameSpecifier *buildSimpleTemplateName(SourceRange SR) {
943 auto NameSpecifierTokens = Builder.getRange(Range: SR);
944 // TODO: Build `SimpleTemplateNameSpecifier` children and implement
945 // accessors to them.
946 // Be aware, we cannot do that simply by calling `TraverseTypeLoc`,
947 // some `TypeLoc`s have inside them the previous name specifier and
948 // we want to treat them independently.
949 auto *NS = new (allocator()) syntax::SimpleTemplateNameSpecifier;
950 Builder.foldNode(Range: NameSpecifierTokens, New: NS, From: nullptr);
951 return NS;
952 }
953
954 syntax::NameSpecifier *
955 buildNameSpecifier(const NestedNameSpecifierLoc &NNSLoc) {
956 assert(NNSLoc.hasQualifier());
957 switch (NNSLoc.getNestedNameSpecifier().getKind()) {
958 case NestedNameSpecifier::Kind::Global:
959 return new (allocator()) syntax::GlobalNameSpecifier;
960
961 case NestedNameSpecifier::Kind::Namespace:
962 return buildIdentifier(SR: NNSLoc.getLocalSourceRange(), /*DropBack=*/true);
963
964 case NestedNameSpecifier::Kind::Type: {
965 TypeLoc TL = NNSLoc.castAsTypeLoc();
966 switch (TL.getTypeLocClass()) {
967 case TypeLoc::Record:
968 case TypeLoc::InjectedClassName:
969 case TypeLoc::Enum:
970 return buildIdentifier(SR: TL.castAs<TagTypeLoc>().getNameLoc());
971 case TypeLoc::Typedef:
972 return buildIdentifier(SR: TL.castAs<TypedefTypeLoc>().getNameLoc());
973 case TypeLoc::UnresolvedUsing:
974 return buildIdentifier(
975 SR: TL.castAs<UnresolvedUsingTypeLoc>().getNameLoc());
976 case TypeLoc::Using:
977 return buildIdentifier(SR: TL.castAs<UsingTypeLoc>().getNameLoc());
978 case TypeLoc::DependentName:
979 return buildIdentifier(SR: TL.castAs<DependentNameTypeLoc>().getNameLoc());
980 case TypeLoc::TemplateSpecialization: {
981 auto TST = TL.castAs<TemplateSpecializationTypeLoc>();
982 SourceLocation BeginLoc = TST.getTemplateKeywordLoc();
983 if (BeginLoc.isInvalid())
984 BeginLoc = TST.getTemplateNameLoc();
985 return buildSimpleTemplateName(SR: {BeginLoc, TST.getEndLoc()});
986 }
987 case TypeLoc::Decltype: {
988 const auto DTL = TL.castAs<DecltypeTypeLoc>();
989 if (!RecursiveASTVisitor::TraverseDecltypeTypeLoc(
990 TL: DTL, /*TraverseQualifier=*/true))
991 return nullptr;
992 auto *NS = new (allocator()) syntax::DecltypeNameSpecifier;
993 // TODO: Implement accessor to `DecltypeNameSpecifier` inner
994 // `DecltypeTypeLoc`.
995 // For that add mapping from `TypeLoc` to `syntax::Node*` then:
996 // Builder.markChild(TypeLoc, syntax::NodeRole);
997 Builder.foldNode(Range: Builder.getRange(Range: DTL.getLocalSourceRange()), New: NS,
998 From: nullptr);
999 return NS;
1000 }
1001 default:
1002 return buildIdentifier(SR: TL.getLocalSourceRange());
1003 }
1004 }
1005 default:
1006 // FIXME: Support Microsoft's __super
1007 llvm::report_fatal_error(reason: "We don't yet support the __super specifier",
1008 gen_crash_diag: true);
1009 }
1010 }
1011
1012 // To build syntax tree nodes for NestedNameSpecifierLoc we override
1013 // Traverse instead of WalkUpFrom because we want to traverse the children
1014 // ourselves and build a list instead of a nested tree of name specifier
1015 // prefixes.
1016 bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc QualifierLoc) {
1017 if (!QualifierLoc)
1018 return true;
1019 for (auto It = QualifierLoc; It; /**/) {
1020 auto *NS = buildNameSpecifier(NNSLoc: It);
1021 if (!NS)
1022 return false;
1023 Builder.markChild(N: NS, R: syntax::NodeRole::ListElement);
1024 Builder.markChildToken(Loc: It.getEndLoc(), R: syntax::NodeRole::ListDelimiter);
1025 if (TypeLoc TL = It.getAsTypeLoc())
1026 It = TL.getPrefix();
1027 else
1028 It = It.getAsNamespaceAndPrefix().Prefix;
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, bool TraverseQualifier) {
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 bool TraverseQualifier) {
1397 // In the source code "void (Y::*mp)()" `MemberPointerTypeLoc` corresponds
1398 // to "Y::*" but it points to a `ParenTypeLoc` that corresponds to
1399 // "(Y::*mp)" We thus reverse the order of traversal to get the proper
1400 // syntax structure.
1401 if (!WalkUpFromMemberPointerTypeLoc(L))
1402 return false;
1403 return TraverseTypeLoc(TL: L.getPointeeLoc());
1404 }
1405
1406 bool WalkUpFromMemberPointerTypeLoc(MemberPointerTypeLoc L) {
1407 auto SR = L.getLocalSourceRange();
1408 Builder.foldNode(Range: Builder.getRange(Range: SR),
1409 New: new (allocator()) syntax::MemberPointer, L);
1410 return true;
1411 }
1412
1413 // The code below is very regular, it could even be generated with some
1414 // preprocessor magic. We merely assign roles to the corresponding children
1415 // and fold resulting nodes.
1416 bool WalkUpFromDeclStmt(DeclStmt *S) {
1417 Builder.foldNode(Range: Builder.getStmtRange(S),
1418 New: new (allocator()) syntax::DeclarationStatement, From: S);
1419 return true;
1420 }
1421
1422 bool WalkUpFromNullStmt(NullStmt *S) {
1423 Builder.foldNode(Range: Builder.getStmtRange(S),
1424 New: new (allocator()) syntax::EmptyStatement, From: S);
1425 return true;
1426 }
1427
1428 bool WalkUpFromSwitchStmt(SwitchStmt *S) {
1429 Builder.markChildToken(Loc: S->getSwitchLoc(),
1430 R: syntax::NodeRole::IntroducerKeyword);
1431 Builder.markStmtChild(Child: S->getBody(), Role: syntax::NodeRole::BodyStatement);
1432 Builder.foldNode(Range: Builder.getStmtRange(S),
1433 New: new (allocator()) syntax::SwitchStatement, From: S);
1434 return true;
1435 }
1436
1437 bool WalkUpFromCaseStmt(CaseStmt *S) {
1438 Builder.markChildToken(Loc: S->getKeywordLoc(),
1439 R: syntax::NodeRole::IntroducerKeyword);
1440 Builder.markExprChild(Child: S->getLHS(), Role: syntax::NodeRole::CaseValue);
1441 Builder.markStmtChild(Child: S->getSubStmt(), Role: syntax::NodeRole::BodyStatement);
1442 Builder.foldNode(Range: Builder.getStmtRange(S),
1443 New: new (allocator()) syntax::CaseStatement, From: S);
1444 return true;
1445 }
1446
1447 bool WalkUpFromDefaultStmt(DefaultStmt *S) {
1448 Builder.markChildToken(Loc: S->getKeywordLoc(),
1449 R: syntax::NodeRole::IntroducerKeyword);
1450 Builder.markStmtChild(Child: S->getSubStmt(), Role: syntax::NodeRole::BodyStatement);
1451 Builder.foldNode(Range: Builder.getStmtRange(S),
1452 New: new (allocator()) syntax::DefaultStatement, From: S);
1453 return true;
1454 }
1455
1456 bool WalkUpFromIfStmt(IfStmt *S) {
1457 Builder.markChildToken(Loc: S->getIfLoc(), R: syntax::NodeRole::IntroducerKeyword);
1458 Stmt *ConditionStatement = S->getCond();
1459 if (S->hasVarStorage())
1460 ConditionStatement = S->getConditionVariableDeclStmt();
1461 Builder.markStmtChild(Child: ConditionStatement, Role: syntax::NodeRole::Condition);
1462 Builder.markStmtChild(Child: S->getThen(), Role: syntax::NodeRole::ThenStatement);
1463 Builder.markChildToken(Loc: S->getElseLoc(), R: syntax::NodeRole::ElseKeyword);
1464 Builder.markStmtChild(Child: S->getElse(), Role: syntax::NodeRole::ElseStatement);
1465 Builder.foldNode(Range: Builder.getStmtRange(S),
1466 New: new (allocator()) syntax::IfStatement, From: S);
1467 return true;
1468 }
1469
1470 bool WalkUpFromForStmt(ForStmt *S) {
1471 Builder.markChildToken(Loc: S->getForLoc(), R: syntax::NodeRole::IntroducerKeyword);
1472 Builder.markStmtChild(Child: S->getBody(), Role: syntax::NodeRole::BodyStatement);
1473 Builder.foldNode(Range: Builder.getStmtRange(S),
1474 New: new (allocator()) syntax::ForStatement, From: S);
1475 return true;
1476 }
1477
1478 bool WalkUpFromWhileStmt(WhileStmt *S) {
1479 Builder.markChildToken(Loc: S->getWhileLoc(),
1480 R: syntax::NodeRole::IntroducerKeyword);
1481 Builder.markStmtChild(Child: S->getBody(), Role: syntax::NodeRole::BodyStatement);
1482 Builder.foldNode(Range: Builder.getStmtRange(S),
1483 New: new (allocator()) syntax::WhileStatement, From: S);
1484 return true;
1485 }
1486
1487 bool WalkUpFromContinueStmt(ContinueStmt *S) {
1488 Builder.markChildToken(Loc: S->getKwLoc(), 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->getKwLoc(), R: syntax::NodeRole::IntroducerKeyword);
1496 Builder.foldNode(Range: Builder.getStmtRange(S),
1497 New: new (allocator()) syntax::BreakStatement, From: S);
1498 return true;
1499 }
1500
1501 bool WalkUpFromReturnStmt(ReturnStmt *S) {
1502 Builder.markChildToken(Loc: S->getReturnLoc(),
1503 R: syntax::NodeRole::IntroducerKeyword);
1504 Builder.markExprChild(Child: S->getRetValue(), Role: syntax::NodeRole::ReturnValue);
1505 Builder.foldNode(Range: Builder.getStmtRange(S),
1506 New: new (allocator()) syntax::ReturnStatement, From: S);
1507 return true;
1508 }
1509
1510 bool WalkUpFromCXXForRangeStmt(CXXForRangeStmt *S) {
1511 Builder.markChildToken(Loc: S->getForLoc(), R: syntax::NodeRole::IntroducerKeyword);
1512 Builder.markStmtChild(Child: S->getBody(), Role: syntax::NodeRole::BodyStatement);
1513 Builder.foldNode(Range: Builder.getStmtRange(S),
1514 New: new (allocator()) syntax::RangeBasedForStatement, From: S);
1515 return true;
1516 }
1517
1518 bool WalkUpFromEmptyDecl(EmptyDecl *S) {
1519 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1520 New: new (allocator()) syntax::EmptyDeclaration, From: S);
1521 return true;
1522 }
1523
1524 bool WalkUpFromStaticAssertDecl(StaticAssertDecl *S) {
1525 Builder.markExprChild(Child: S->getAssertExpr(), Role: syntax::NodeRole::Condition);
1526 Builder.markExprChild(Child: S->getMessage(), Role: syntax::NodeRole::Message);
1527 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1528 New: new (allocator()) syntax::StaticAssertDeclaration, From: S);
1529 return true;
1530 }
1531
1532 bool WalkUpFromLinkageSpecDecl(LinkageSpecDecl *S) {
1533 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1534 New: new (allocator()) syntax::LinkageSpecificationDeclaration,
1535 From: S);
1536 return true;
1537 }
1538
1539 bool WalkUpFromNamespaceAliasDecl(NamespaceAliasDecl *S) {
1540 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1541 New: new (allocator()) syntax::NamespaceAliasDefinition, From: S);
1542 return true;
1543 }
1544
1545 bool WalkUpFromUsingDirectiveDecl(UsingDirectiveDecl *S) {
1546 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1547 New: new (allocator()) syntax::UsingNamespaceDirective, From: S);
1548 return true;
1549 }
1550
1551 bool WalkUpFromUsingDecl(UsingDecl *S) {
1552 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1553 New: new (allocator()) syntax::UsingDeclaration, From: S);
1554 return true;
1555 }
1556
1557 bool WalkUpFromUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *S) {
1558 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1559 New: new (allocator()) syntax::UsingDeclaration, From: S);
1560 return true;
1561 }
1562
1563 bool WalkUpFromUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *S) {
1564 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1565 New: new (allocator()) syntax::UsingDeclaration, From: S);
1566 return true;
1567 }
1568
1569 bool WalkUpFromTypeAliasDecl(TypeAliasDecl *S) {
1570 Builder.foldNode(Range: Builder.getDeclarationRange(D: S),
1571 New: new (allocator()) syntax::TypeAliasDeclaration, From: S);
1572 return true;
1573 }
1574
1575private:
1576 /// Folds SimpleDeclarator node (if present) and in case this is the last
1577 /// declarator in the chain it also folds SimpleDeclaration node.
1578 template <class T> bool processDeclaratorAndDeclaration(T *D) {
1579 auto Range = getDeclaratorRange(
1580 Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
1581 getQualifiedNameStart(D), getInitializerRange(D));
1582
1583 // There doesn't have to be a declarator (e.g. `void foo(int)` only has
1584 // declaration, but no declarator).
1585 if (!Range.getBegin().isValid()) {
1586 Builder.markChild(N: new (allocator()) syntax::DeclaratorList,
1587 R: syntax::NodeRole::Declarators);
1588 Builder.foldNode(Builder.getDeclarationRange(D),
1589 new (allocator()) syntax::SimpleDeclaration, D);
1590 return true;
1591 }
1592
1593 auto *N = new (allocator()) syntax::SimpleDeclarator;
1594 Builder.foldNode(Builder.getRange(Range), N, nullptr);
1595 Builder.markChild(N, R: syntax::NodeRole::ListElement);
1596
1597 if (!Builder.isResponsibleForCreatingDeclaration(D)) {
1598 // If this is not the last declarator in the declaration we expect a
1599 // delimiter after it.
1600 const auto *DelimiterToken = std::next(Builder.findToken(L: Range.getEnd()));
1601 if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1602 Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1603 } else {
1604 auto *DL = new (allocator()) syntax::DeclaratorList;
1605 auto DeclarationRange = Builder.getDeclarationRange(D);
1606 Builder.foldList(SuperRange: DeclarationRange, New: DL, From: nullptr);
1607
1608 Builder.markChild(N: DL, R: syntax::NodeRole::Declarators);
1609 Builder.foldNode(DeclarationRange,
1610 new (allocator()) syntax::SimpleDeclaration, D);
1611 }
1612 return true;
1613 }
1614
1615 /// Returns the range of the built node.
1616 syntax::TrailingReturnType *buildTrailingReturn(FunctionProtoTypeLoc L) {
1617 assert(L.getTypePtr()->hasTrailingReturn());
1618
1619 auto ReturnedType = L.getReturnLoc();
1620 // Build node for the declarator, if any.
1621 auto ReturnDeclaratorRange = SourceRange(GetStartLoc().Visit(TyLoc: ReturnedType),
1622 ReturnedType.getEndLoc());
1623 syntax::SimpleDeclarator *ReturnDeclarator = nullptr;
1624 if (ReturnDeclaratorRange.isValid()) {
1625 ReturnDeclarator = new (allocator()) syntax::SimpleDeclarator;
1626 Builder.foldNode(Range: Builder.getRange(Range: ReturnDeclaratorRange),
1627 New: ReturnDeclarator, From: nullptr);
1628 }
1629
1630 // Build node for trailing return type.
1631 auto Return = Builder.getRange(Range: ReturnedType.getSourceRange());
1632 const auto *Arrow = Return.begin() - 1;
1633 assert(Arrow->kind() == tok::arrow);
1634 auto Tokens = llvm::ArrayRef(Arrow, Return.end());
1635 Builder.markChildToken(T: Arrow, R: syntax::NodeRole::ArrowToken);
1636 if (ReturnDeclarator)
1637 Builder.markChild(N: ReturnDeclarator, R: syntax::NodeRole::Declarator);
1638 auto *R = new (allocator()) syntax::TrailingReturnType;
1639 Builder.foldNode(Range: Tokens, New: R, L);
1640 return R;
1641 }
1642
1643 void foldExplicitTemplateInstantiation(
1644 ArrayRef<syntax::Token> Range, const syntax::Token *ExternKW,
1645 const syntax::Token *TemplateKW,
1646 syntax::SimpleDeclaration *InnerDeclaration, Decl *From) {
1647 assert(!ExternKW || ExternKW->kind() == tok::kw_extern);
1648 assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
1649 Builder.markChildToken(T: ExternKW, R: syntax::NodeRole::ExternKeyword);
1650 Builder.markChildToken(T: TemplateKW, R: syntax::NodeRole::IntroducerKeyword);
1651 Builder.markChild(N: InnerDeclaration, R: syntax::NodeRole::Declaration);
1652 Builder.foldNode(
1653 Range, New: new (allocator()) syntax::ExplicitTemplateInstantiation, From);
1654 }
1655
1656 syntax::TemplateDeclaration *foldTemplateDeclaration(
1657 ArrayRef<syntax::Token> Range, const syntax::Token *TemplateKW,
1658 ArrayRef<syntax::Token> TemplatedDeclaration, Decl *From) {
1659 assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
1660 Builder.markChildToken(T: TemplateKW, R: syntax::NodeRole::IntroducerKeyword);
1661
1662 auto *N = new (allocator()) syntax::TemplateDeclaration;
1663 Builder.foldNode(Range, New: N, From);
1664 Builder.markChild(N, R: syntax::NodeRole::Declaration);
1665 return N;
1666 }
1667
1668 /// A small helper to save some typing.
1669 llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }
1670
1671 syntax::TreeBuilder &Builder;
1672 const ASTContext &Context;
1673};
1674} // namespace
1675
1676void syntax::TreeBuilder::noticeDeclWithoutSemicolon(Decl *D) {
1677 DeclsWithoutSemicolons.insert(V: D);
1678}
1679
1680void syntax::TreeBuilder::markChildToken(SourceLocation Loc, NodeRole Role) {
1681 if (Loc.isInvalid())
1682 return;
1683 Pending.assignRole(Range: *findToken(L: Loc), Role);
1684}
1685
1686void syntax::TreeBuilder::markChildToken(const syntax::Token *T, NodeRole R) {
1687 if (!T)
1688 return;
1689 Pending.assignRole(Range: *T, Role: R);
1690}
1691
1692void syntax::TreeBuilder::markChild(syntax::Node *N, NodeRole R) {
1693 assert(N);
1694 setRole(N, R);
1695}
1696
1697void syntax::TreeBuilder::markChild(ASTPtr N, NodeRole R) {
1698 auto *SN = Mapping.find(P: N);
1699 assert(SN != nullptr);
1700 setRole(N: SN, R);
1701}
1702void syntax::TreeBuilder::markChild(NestedNameSpecifierLoc NNSLoc, NodeRole R) {
1703 auto *SN = Mapping.find(P: NNSLoc);
1704 assert(SN != nullptr);
1705 setRole(N: SN, R);
1706}
1707
1708void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
1709 if (!Child)
1710 return;
1711
1712 syntax::Tree *ChildNode;
1713 if (Expr *ChildExpr = dyn_cast<Expr>(Val: Child)) {
1714 // This is an expression in a statement position, consume the trailing
1715 // semicolon and form an 'ExpressionStatement' node.
1716 markExprChild(Child: ChildExpr, Role: NodeRole::Expression);
1717 ChildNode = new (allocator()) syntax::ExpressionStatement;
1718 // (!) 'getStmtRange()' ensures this covers a trailing semicolon.
1719 Pending.foldChildren(TB: TBTM.tokenBuffer(), Tokens: getStmtRange(S: Child), Node: ChildNode);
1720 } else {
1721 ChildNode = Mapping.find(P: Child);
1722 }
1723 assert(ChildNode != nullptr);
1724 setRole(N: ChildNode, R: Role);
1725}
1726
1727void syntax::TreeBuilder::markExprChild(Expr *Child, NodeRole Role) {
1728 if (!Child)
1729 return;
1730 Child = IgnoreImplicit(E: Child);
1731
1732 syntax::Tree *ChildNode = Mapping.find(P: Child);
1733 assert(ChildNode != nullptr);
1734 setRole(N: ChildNode, R: Role);
1735}
1736
1737const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {
1738 if (L.isInvalid())
1739 return nullptr;
1740 auto It = LocationToToken.find(Val: L);
1741 assert(It != LocationToToken.end());
1742 return It->second;
1743}
1744
1745syntax::TranslationUnit *syntax::buildSyntaxTree(Arena &A,
1746 TokenBufferTokenManager& TBTM,
1747 ASTContext &Context) {
1748 TreeBuilder Builder(A, TBTM);
1749 BuildTreeVisitor(Context, Builder).TraverseAST(AST&: Context);
1750 return std::move(Builder).finalize();
1751}
1752