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