xref: /freebsd/contrib/llvm-project/clang/lib/Tooling/Syntax/BuildTree.cpp (revision 19261079b74319502c6ffa1249920079f0f69a72)
1 //===- BuildTree.cpp ------------------------------------------*- C++ -*-=====//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 #include "clang/Tooling/Syntax/BuildTree.h"
9 #include "clang/AST/ASTFwd.h"
10 #include "clang/AST/Decl.h"
11 #include "clang/AST/DeclBase.h"
12 #include "clang/AST/DeclCXX.h"
13 #include "clang/AST/DeclarationName.h"
14 #include "clang/AST/Expr.h"
15 #include "clang/AST/ExprCXX.h"
16 #include "clang/AST/IgnoreExpr.h"
17 #include "clang/AST/OperationKinds.h"
18 #include "clang/AST/RecursiveASTVisitor.h"
19 #include "clang/AST/Stmt.h"
20 #include "clang/AST/TypeLoc.h"
21 #include "clang/AST/TypeLocVisitor.h"
22 #include "clang/Basic/LLVM.h"
23 #include "clang/Basic/SourceLocation.h"
24 #include "clang/Basic/SourceManager.h"
25 #include "clang/Basic/Specifiers.h"
26 #include "clang/Basic/TokenKinds.h"
27 #include "clang/Lex/Lexer.h"
28 #include "clang/Lex/LiteralSupport.h"
29 #include "clang/Tooling/Syntax/Nodes.h"
30 #include "clang/Tooling/Syntax/Tokens.h"
31 #include "clang/Tooling/Syntax/Tree.h"
32 #include "llvm/ADT/ArrayRef.h"
33 #include "llvm/ADT/DenseMap.h"
34 #include "llvm/ADT/PointerUnion.h"
35 #include "llvm/ADT/STLExtras.h"
36 #include "llvm/ADT/ScopeExit.h"
37 #include "llvm/ADT/SmallVector.h"
38 #include "llvm/Support/Allocator.h"
39 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/Compiler.h"
41 #include "llvm/Support/FormatVariadic.h"
42 #include "llvm/Support/MemoryBuffer.h"
43 #include "llvm/Support/raw_ostream.h"
44 #include <cstddef>
45 #include <map>
46 
47 using namespace clang;
48 
49 // Ignores the implicit `CXXConstructExpr` for copy/move constructor calls
50 // generated by the compiler, as well as in implicit conversions like the one
51 // wrapping `1` in `X x = 1;`.
52 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)`.
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 
79 static Expr *IgnoreImplicit(Expr *E) {
80   return IgnoreExprNodes(E, IgnoreImplicitSingleStep,
81                          IgnoreImplicitConstructorSingleStep,
82                          IgnoreCXXFunctionalCastExprWrappingConstructor);
83 }
84 
85 LLVM_ATTRIBUTE_UNUSED
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> {
102   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.
110   SourceLocation VisitPointerTypeLoc(PointerTypeLoc T) {
111     return HandlePointer(T);
112   }
113 
114   SourceLocation VisitMemberPointerTypeLoc(MemberPointerTypeLoc T) {
115     return HandlePointer(T);
116   }
117 
118   SourceLocation VisitBlockPointerTypeLoc(BlockPointerTypeLoc T) {
119     return HandlePointer(T);
120   }
121 
122   SourceLocation VisitReferenceTypeLoc(ReferenceTypeLoc T) {
123     return HandlePointer(T);
124   }
125 
126   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.
134   SourceLocation VisitTypeLoc(TypeLoc T) {
135     auto N = T.getNextTypeLoc();
136     if (!N)
137       return SourceLocation();
138     return Visit(N);
139   }
140 
141   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:
148   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 
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 
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(){}`
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 `()`.
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.
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   assert(End.isValid());
298   if (Name.isValid()) {
299     if (Start.isInvalid())
300       Start = Name;
301     if (SM.isBeforeInTranslationUnit(End, Name))
302       End = Name;
303   }
304   if (Initializer.isValid()) {
305     auto InitializerEnd = Initializer.getEnd();
306     assert(SM.isBeforeInTranslationUnit(End, InitializerEnd) ||
307            End == InitializerEnd);
308     End = InitializerEnd;
309   }
310   return SourceRange(Start, End);
311 }
312 
313 namespace {
314 /// All AST hierarchy roots that can be represented as pointers.
315 using ASTPtr = llvm::PointerUnion<Stmt *, Decl *>;
316 /// Maintains a mapping from AST to syntax tree nodes. This class will get more
317 /// complicated as we support more kinds of AST nodes, e.g. TypeLocs.
318 /// FIXME: expose this as public API.
319 class ASTToSyntaxMapping {
320 public:
321   void add(ASTPtr From, syntax::Tree *To) {
322     assert(To != nullptr);
323     assert(!From.isNull());
324 
325     bool Added = Nodes.insert({From, To}).second;
326     (void)Added;
327     assert(Added && "mapping added twice");
328   }
329 
330   void add(NestedNameSpecifierLoc From, syntax::Tree *To) {
331     assert(To != nullptr);
332     assert(From.hasQualifier());
333 
334     bool Added = NNSNodes.insert({From, To}).second;
335     (void)Added;
336     assert(Added && "mapping added twice");
337   }
338 
339   syntax::Tree *find(ASTPtr P) const { return Nodes.lookup(P); }
340 
341   syntax::Tree *find(NestedNameSpecifierLoc P) const {
342     return NNSNodes.lookup(P);
343   }
344 
345 private:
346   llvm::DenseMap<ASTPtr, syntax::Tree *> Nodes;
347   llvm::DenseMap<NestedNameSpecifierLoc, syntax::Tree *> NNSNodes;
348 };
349 } // namespace
350 
351 /// A helper class for constructing the syntax tree while traversing a clang
352 /// AST.
353 ///
354 /// At each point of the traversal we maintain a list of pending nodes.
355 /// Initially all tokens are added as pending nodes. When processing a clang AST
356 /// node, the clients need to:
357 ///   - create a corresponding syntax node,
358 ///   - assign roles to all pending child nodes with 'markChild' and
359 ///     'markChildToken',
360 ///   - replace the child nodes with the new syntax node in the pending list
361 ///     with 'foldNode'.
362 ///
363 /// Note that all children are expected to be processed when building a node.
364 ///
365 /// Call finalize() to finish building the tree and consume the root node.
366 class syntax::TreeBuilder {
367 public:
368   TreeBuilder(syntax::Arena &Arena) : Arena(Arena), Pending(Arena) {
369     for (const auto &T : Arena.getTokenBuffer().expandedTokens())
370       LocationToToken.insert({T.location(), &T});
371   }
372 
373   llvm::BumpPtrAllocator &allocator() { return Arena.getAllocator(); }
374   const SourceManager &sourceManager() const {
375     return Arena.getSourceManager();
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(Arena, Range, New);
383     if (From)
384       Mapping.add(From, 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, nullptr);
390   }
391 
392   void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
393                 NestedNameSpecifierLoc From) {
394     assert(New);
395     Pending.foldChildren(Arena, Range, New);
396     if (From)
397       Mapping.add(From, 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(SuperRange);
406     Pending.foldChildren(Arena, ListRange, New);
407     if (From)
408       Mapping.add(From, 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 = Arena.getTokenBuffer().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(Arena, Tokens.drop_back(),
443                          new (Arena.getAllocator()) syntax::TranslationUnit);
444 
445     auto *TU = cast<syntax::TranslationUnit>(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(Range.getBegin(), 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            Arena.getSourceManager().isBeforeInTranslationUnit(First, Last));
468     return llvm::makeArrayRef(findToken(First), std::next(findToken(Last)));
469   }
470 
471   ArrayRef<syntax::Token>
472   getTemplateRange(const ClassTemplateSpecializationDecl *D) const {
473     auto Tokens = getRange(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>(D))
509       Tokens = getRange(S->TypeDecl::getBeginLoc(), S->getEndLoc());
510     else
511       Tokens = getRange(D->getSourceRange());
512     return maybeAppendSemicolon(Tokens, D);
513   }
514 
515   ArrayRef<syntax::Token> getExprRange(const Expr *E) const {
516     return getRange(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(S->getSourceRange());
523     if (isa<CompoundStmt>(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 
533 private:
534   ArrayRef<syntax::Token> maybeAppendSemicolon(ArrayRef<syntax::Token> Tokens,
535                                                const Decl *D) const {
536     if (isa<NamespaceDecl>(D))
537       return Tokens;
538     if (DeclsWithoutSemicolons.count(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::makeArrayRef(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) {
568       assert(!A.getTokenBuffer().expandedTokens().empty());
569       assert(A.getTokenBuffer().expandedTokens().back().kind() == tok::eof);
570       // Create all leaf nodes.
571       // Note that we do not have 'eof' in the tree.
572       for (const auto &T : A.getTokenBuffer().expandedTokens().drop_back()) {
573         auto *L = new (A.getAllocator()) syntax::Leaf(&T);
574         L->Original = true;
575         L->CanModify = A.getTokenBuffer().spelledForExpanded(T).hasValue();
576         Trees.insert(Trees.end(), {&T, L});
577       }
578     }
579 
580     void assignRole(ArrayRef<syntax::Token> Range, syntax::NodeRole Role) {
581       assert(!Range.empty());
582       auto It = Trees.lower_bound(Range.begin());
583       assert(It != Trees.end() && "no node found");
584       assert(It->first == Range.begin() && "no child with the specified range");
585       assert((std::next(It) == Trees.end() ||
586               std::next(It)->first == Range.end()) &&
587              "no child with the specified range");
588       assert(It->second->getRole() == NodeRole::Detached &&
589              "re-assigning role for a child");
590       It->second->setRole(Role);
591     }
592 
593     /// Shrink \p Range to a subrange that only contains tokens of a list.
594     /// List elements and delimiters should already have correct roles.
595     ArrayRef<syntax::Token> shrinkToFitList(ArrayRef<syntax::Token> Range) {
596       auto BeginChildren = Trees.lower_bound(Range.begin());
597       assert((BeginChildren == Trees.end() ||
598               BeginChildren->first == Range.begin()) &&
599              "Range crosses boundaries of existing subtrees");
600 
601       auto EndChildren = Trees.lower_bound(Range.end());
602       assert(
603           (EndChildren == Trees.end() || EndChildren->first == Range.end()) &&
604           "Range crosses boundaries of existing subtrees");
605 
606       auto BelongsToList = [](decltype(Trees)::value_type KV) {
607         auto Role = KV.second->getRole();
608         return Role == syntax::NodeRole::ListElement ||
609                Role == syntax::NodeRole::ListDelimiter;
610       };
611 
612       auto BeginListChildren =
613           std::find_if(BeginChildren, EndChildren, BelongsToList);
614 
615       auto EndListChildren =
616           std::find_if_not(BeginListChildren, EndChildren, BelongsToList);
617 
618       return ArrayRef<syntax::Token>(BeginListChildren->first,
619                                      EndListChildren->first);
620     }
621 
622     /// Add \p Node to the forest and attach child nodes based on \p Tokens.
623     void foldChildren(const syntax::Arena &A, ArrayRef<syntax::Token> Tokens,
624                       syntax::Tree *Node) {
625       // Attach children to `Node`.
626       assert(Node->getFirstChild() == nullptr && "node already has children");
627 
628       auto *FirstToken = Tokens.begin();
629       auto BeginChildren = Trees.lower_bound(FirstToken);
630 
631       assert((BeginChildren == Trees.end() ||
632               BeginChildren->first == FirstToken) &&
633              "fold crosses boundaries of existing subtrees");
634       auto EndChildren = Trees.lower_bound(Tokens.end());
635       assert(
636           (EndChildren == Trees.end() || EndChildren->first == Tokens.end()) &&
637           "fold crosses boundaries of existing subtrees");
638 
639       for (auto It = BeginChildren; It != EndChildren; ++It) {
640         auto *C = It->second;
641         if (C->getRole() == NodeRole::Detached)
642           C->setRole(NodeRole::Unknown);
643         Node->appendChildLowLevel(C);
644       }
645 
646       // Mark that this node came from the AST and is backed by the source code.
647       Node->Original = true;
648       Node->CanModify =
649           A.getTokenBuffer().spelledForExpanded(Tokens).hasValue();
650 
651       Trees.erase(BeginChildren, EndChildren);
652       Trees.insert({FirstToken, Node});
653     }
654 
655     // EXPECTS: all tokens were consumed and are owned by a single root node.
656     syntax::Node *finalize() && {
657       assert(Trees.size() == 1);
658       auto *Root = Trees.begin()->second;
659       Trees = {};
660       return Root;
661     }
662 
663     std::string str(const syntax::Arena &A) const {
664       std::string R;
665       for (auto It = Trees.begin(); It != Trees.end(); ++It) {
666         unsigned CoveredTokens =
667             It != Trees.end()
668                 ? (std::next(It)->first - It->first)
669                 : A.getTokenBuffer().expandedTokens().end() - It->first;
670 
671         R += std::string(
672             formatv("- '{0}' covers '{1}'+{2} tokens\n", It->second->getKind(),
673                     It->first->text(A.getSourceManager()), CoveredTokens));
674         R += It->second->dump(A.getSourceManager());
675       }
676       return R;
677     }
678 
679   private:
680     /// Maps from the start token to a subtree starting at that token.
681     /// Keys in the map are pointers into the array of expanded tokens, so
682     /// pointer order corresponds to the order of preprocessor tokens.
683     std::map<const syntax::Token *, syntax::Node *> Trees;
684   };
685 
686   /// For debugging purposes.
687   std::string str() { return Pending.str(Arena); }
688 
689   syntax::Arena &Arena;
690   /// To quickly find tokens by their start location.
691   llvm::DenseMap<SourceLocation, const syntax::Token *> LocationToToken;
692   Forest Pending;
693   llvm::DenseSet<Decl *> DeclsWithoutSemicolons;
694   ASTToSyntaxMapping Mapping;
695 };
696 
697 namespace {
698 class BuildTreeVisitor : public RecursiveASTVisitor<BuildTreeVisitor> {
699 public:
700   explicit BuildTreeVisitor(ASTContext &Context, syntax::TreeBuilder &Builder)
701       : Builder(Builder), Context(Context) {}
702 
703   bool shouldTraversePostOrder() const { return true; }
704 
705   bool WalkUpFromDeclaratorDecl(DeclaratorDecl *DD) {
706     return processDeclaratorAndDeclaration(DD);
707   }
708 
709   bool WalkUpFromTypedefNameDecl(TypedefNameDecl *TD) {
710     return processDeclaratorAndDeclaration(TD);
711   }
712 
713   bool VisitDecl(Decl *D) {
714     assert(!D->isImplicit());
715     Builder.foldNode(Builder.getDeclarationRange(D),
716                      new (allocator()) syntax::UnknownDeclaration(), D);
717     return true;
718   }
719 
720   // RAV does not call WalkUpFrom* on explicit instantiations, so we have to
721   // override Traverse.
722   // FIXME: make RAV call WalkUpFrom* instead.
723   bool
724   TraverseClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *C) {
725     if (!RecursiveASTVisitor::TraverseClassTemplateSpecializationDecl(C))
726       return false;
727     if (C->isExplicitSpecialization())
728       return true; // we are only interested in explicit instantiations.
729     auto *Declaration =
730         cast<syntax::SimpleDeclaration>(handleFreeStandingTagDecl(C));
731     foldExplicitTemplateInstantiation(
732         Builder.getTemplateRange(C), Builder.findToken(C->getExternLoc()),
733         Builder.findToken(C->getTemplateKeywordLoc()), Declaration, C);
734     return true;
735   }
736 
737   bool WalkUpFromTemplateDecl(TemplateDecl *S) {
738     foldTemplateDeclaration(
739         Builder.getDeclarationRange(S),
740         Builder.findToken(S->getTemplateParameters()->getTemplateLoc()),
741         Builder.getDeclarationRange(S->getTemplatedDecl()), S);
742     return true;
743   }
744 
745   bool WalkUpFromTagDecl(TagDecl *C) {
746     // FIXME: build the ClassSpecifier node.
747     if (!C->isFreeStanding()) {
748       assert(C->getNumTemplateParameterLists() == 0);
749       return true;
750     }
751     handleFreeStandingTagDecl(C);
752     return true;
753   }
754 
755   syntax::Declaration *handleFreeStandingTagDecl(TagDecl *C) {
756     assert(C->isFreeStanding());
757     // Class is a declaration specifier and needs a spanning declaration node.
758     auto DeclarationRange = Builder.getDeclarationRange(C);
759     syntax::Declaration *Result = new (allocator()) syntax::SimpleDeclaration;
760     Builder.foldNode(DeclarationRange, Result, nullptr);
761 
762     // Build TemplateDeclaration nodes if we had template parameters.
763     auto ConsumeTemplateParameters = [&](const TemplateParameterList &L) {
764       const auto *TemplateKW = Builder.findToken(L.getTemplateLoc());
765       auto R = llvm::makeArrayRef(TemplateKW, DeclarationRange.end());
766       Result =
767           foldTemplateDeclaration(R, TemplateKW, DeclarationRange, nullptr);
768       DeclarationRange = R;
769     };
770     if (auto *S = dyn_cast<ClassTemplatePartialSpecializationDecl>(C))
771       ConsumeTemplateParameters(*S->getTemplateParameters());
772     for (unsigned I = C->getNumTemplateParameterLists(); 0 < I; --I)
773       ConsumeTemplateParameters(*C->getTemplateParameterList(I - 1));
774     return Result;
775   }
776 
777   bool WalkUpFromTranslationUnitDecl(TranslationUnitDecl *TU) {
778     // We do not want to call VisitDecl(), the declaration for translation
779     // unit is built by finalize().
780     return true;
781   }
782 
783   bool WalkUpFromCompoundStmt(CompoundStmt *S) {
784     using NodeRole = syntax::NodeRole;
785 
786     Builder.markChildToken(S->getLBracLoc(), NodeRole::OpenParen);
787     for (auto *Child : S->body())
788       Builder.markStmtChild(Child, NodeRole::Statement);
789     Builder.markChildToken(S->getRBracLoc(), NodeRole::CloseParen);
790 
791     Builder.foldNode(Builder.getStmtRange(S),
792                      new (allocator()) syntax::CompoundStatement, S);
793     return true;
794   }
795 
796   // Some statements are not yet handled by syntax trees.
797   bool WalkUpFromStmt(Stmt *S) {
798     Builder.foldNode(Builder.getStmtRange(S),
799                      new (allocator()) syntax::UnknownStatement, S);
800     return true;
801   }
802 
803   bool TraverseCXXForRangeStmt(CXXForRangeStmt *S) {
804     // We override to traverse range initializer as VarDecl.
805     // RAV traverses it as a statement, we produce invalid node kinds in that
806     // case.
807     // FIXME: should do this in RAV instead?
808     bool Result = [&, this]() {
809       if (S->getInit() && !TraverseStmt(S->getInit()))
810         return false;
811       if (S->getLoopVariable() && !TraverseDecl(S->getLoopVariable()))
812         return false;
813       if (S->getRangeInit() && !TraverseStmt(S->getRangeInit()))
814         return false;
815       if (S->getBody() && !TraverseStmt(S->getBody()))
816         return false;
817       return true;
818     }();
819     WalkUpFromCXXForRangeStmt(S);
820     return Result;
821   }
822 
823   bool TraverseStmt(Stmt *S) {
824     if (auto *DS = dyn_cast_or_null<DeclStmt>(S)) {
825       // We want to consume the semicolon, make sure SimpleDeclaration does not.
826       for (auto *D : DS->decls())
827         Builder.noticeDeclWithoutSemicolon(D);
828     } else if (auto *E = dyn_cast_or_null<Expr>(S)) {
829       return RecursiveASTVisitor::TraverseStmt(IgnoreImplicit(E));
830     }
831     return RecursiveASTVisitor::TraverseStmt(S);
832   }
833 
834   // Some expressions are not yet handled by syntax trees.
835   bool WalkUpFromExpr(Expr *E) {
836     assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");
837     Builder.foldNode(Builder.getExprRange(E),
838                      new (allocator()) syntax::UnknownExpression, E);
839     return true;
840   }
841 
842   bool TraverseUserDefinedLiteral(UserDefinedLiteral *S) {
843     // The semantic AST node `UserDefinedLiteral` (UDL) may have one child node
844     // referencing the location of the UDL suffix (`_w` in `1.2_w`). The
845     // UDL suffix location does not point to the beginning of a token, so we
846     // can't represent the UDL suffix as a separate syntax tree node.
847 
848     return WalkUpFromUserDefinedLiteral(S);
849   }
850 
851   syntax::UserDefinedLiteralExpression *
852   buildUserDefinedLiteral(UserDefinedLiteral *S) {
853     switch (S->getLiteralOperatorKind()) {
854     case UserDefinedLiteral::LOK_Integer:
855       return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;
856     case UserDefinedLiteral::LOK_Floating:
857       return new (allocator()) syntax::FloatUserDefinedLiteralExpression;
858     case UserDefinedLiteral::LOK_Character:
859       return new (allocator()) syntax::CharUserDefinedLiteralExpression;
860     case UserDefinedLiteral::LOK_String:
861       return new (allocator()) syntax::StringUserDefinedLiteralExpression;
862     case UserDefinedLiteral::LOK_Raw:
863     case UserDefinedLiteral::LOK_Template:
864       // For raw literal operator and numeric literal operator template we
865       // cannot get the type of the operand in the semantic AST. We get this
866       // information from the token. As integer and floating point have the same
867       // token kind, we run `NumericLiteralParser` again to distinguish them.
868       auto TokLoc = S->getBeginLoc();
869       auto TokSpelling =
870           Builder.findToken(TokLoc)->text(Context.getSourceManager());
871       auto Literal =
872           NumericLiteralParser(TokSpelling, TokLoc, Context.getSourceManager(),
873                                Context.getLangOpts(), Context.getTargetInfo(),
874                                Context.getDiagnostics());
875       if (Literal.isIntegerLiteral())
876         return new (allocator()) syntax::IntegerUserDefinedLiteralExpression;
877       else {
878         assert(Literal.isFloatingLiteral());
879         return new (allocator()) syntax::FloatUserDefinedLiteralExpression;
880       }
881     }
882     llvm_unreachable("Unknown literal operator kind.");
883   }
884 
885   bool WalkUpFromUserDefinedLiteral(UserDefinedLiteral *S) {
886     Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);
887     Builder.foldNode(Builder.getExprRange(S), buildUserDefinedLiteral(S), S);
888     return true;
889   }
890 
891   // FIXME: Fix `NestedNameSpecifierLoc::getLocalSourceRange` for the
892   // `DependentTemplateSpecializationType` case.
893   /// Given a nested-name-specifier return the range for the last name
894   /// specifier.
895   ///
896   /// e.g. `std::T::template X<U>::` => `template X<U>::`
897   SourceRange getLocalSourceRange(const NestedNameSpecifierLoc &NNSLoc) {
898     auto SR = NNSLoc.getLocalSourceRange();
899 
900     // The method `NestedNameSpecifierLoc::getLocalSourceRange` *should*
901     // return the desired `SourceRange`, but there is a corner case. For a
902     // `DependentTemplateSpecializationType` this method returns its
903     // qualifiers as well, in other words in the example above this method
904     // returns `T::template X<U>::` instead of only `template X<U>::`
905     if (auto TL = NNSLoc.getTypeLoc()) {
906       if (auto DependentTL =
907               TL.getAs<DependentTemplateSpecializationTypeLoc>()) {
908         // The 'template' keyword is always present in dependent template
909         // specializations. Except in the case of incorrect code
910         // TODO: Treat the case of incorrect code.
911         SR.setBegin(DependentTL.getTemplateKeywordLoc());
912       }
913     }
914 
915     return SR;
916   }
917 
918   syntax::NodeKind getNameSpecifierKind(const NestedNameSpecifier &NNS) {
919     switch (NNS.getKind()) {
920     case NestedNameSpecifier::Global:
921       return syntax::NodeKind::GlobalNameSpecifier;
922     case NestedNameSpecifier::Namespace:
923     case NestedNameSpecifier::NamespaceAlias:
924     case NestedNameSpecifier::Identifier:
925       return syntax::NodeKind::IdentifierNameSpecifier;
926     case NestedNameSpecifier::TypeSpecWithTemplate:
927       return syntax::NodeKind::SimpleTemplateNameSpecifier;
928     case NestedNameSpecifier::TypeSpec: {
929       const auto *NNSType = NNS.getAsType();
930       assert(NNSType);
931       if (isa<DecltypeType>(NNSType))
932         return syntax::NodeKind::DecltypeNameSpecifier;
933       if (isa<TemplateSpecializationType, DependentTemplateSpecializationType>(
934               NNSType))
935         return syntax::NodeKind::SimpleTemplateNameSpecifier;
936       return syntax::NodeKind::IdentifierNameSpecifier;
937     }
938     default:
939       // FIXME: Support Microsoft's __super
940       llvm::report_fatal_error("We don't yet support the __super specifier",
941                                true);
942     }
943   }
944 
945   syntax::NameSpecifier *
946   buildNameSpecifier(const NestedNameSpecifierLoc &NNSLoc) {
947     assert(NNSLoc.hasQualifier());
948     auto NameSpecifierTokens =
949         Builder.getRange(getLocalSourceRange(NNSLoc)).drop_back();
950     switch (getNameSpecifierKind(*NNSLoc.getNestedNameSpecifier())) {
951     case syntax::NodeKind::GlobalNameSpecifier:
952       return new (allocator()) syntax::GlobalNameSpecifier;
953     case syntax::NodeKind::IdentifierNameSpecifier: {
954       assert(NameSpecifierTokens.size() == 1);
955       Builder.markChildToken(NameSpecifierTokens.begin(),
956                              syntax::NodeRole::Unknown);
957       auto *NS = new (allocator()) syntax::IdentifierNameSpecifier;
958       Builder.foldNode(NameSpecifierTokens, NS, nullptr);
959       return NS;
960     }
961     case syntax::NodeKind::SimpleTemplateNameSpecifier: {
962       // TODO: Build `SimpleTemplateNameSpecifier` children and implement
963       // accessors to them.
964       // Be aware, we cannot do that simply by calling `TraverseTypeLoc`,
965       // some `TypeLoc`s have inside them the previous name specifier and
966       // we want to treat them independently.
967       auto *NS = new (allocator()) syntax::SimpleTemplateNameSpecifier;
968       Builder.foldNode(NameSpecifierTokens, NS, nullptr);
969       return NS;
970     }
971     case syntax::NodeKind::DecltypeNameSpecifier: {
972       const auto TL = NNSLoc.getTypeLoc().castAs<DecltypeTypeLoc>();
973       if (!RecursiveASTVisitor::TraverseDecltypeTypeLoc(TL))
974         return nullptr;
975       auto *NS = new (allocator()) syntax::DecltypeNameSpecifier;
976       // TODO: Implement accessor to `DecltypeNameSpecifier` inner
977       // `DecltypeTypeLoc`.
978       // For that add mapping from `TypeLoc` to `syntax::Node*` then:
979       // Builder.markChild(TypeLoc, syntax::NodeRole);
980       Builder.foldNode(NameSpecifierTokens, NS, nullptr);
981       return NS;
982     }
983     default:
984       llvm_unreachable("getChildKind() does not return this value");
985     }
986   }
987 
988   // To build syntax tree nodes for NestedNameSpecifierLoc we override
989   // Traverse instead of WalkUpFrom because we want to traverse the children
990   // ourselves and build a list instead of a nested tree of name specifier
991   // prefixes.
992   bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc QualifierLoc) {
993     if (!QualifierLoc)
994       return true;
995     for (auto It = QualifierLoc; It; It = It.getPrefix()) {
996       auto *NS = buildNameSpecifier(It);
997       if (!NS)
998         return false;
999       Builder.markChild(NS, syntax::NodeRole::ListElement);
1000       Builder.markChildToken(It.getEndLoc(), syntax::NodeRole::ListDelimiter);
1001     }
1002     Builder.foldNode(Builder.getRange(QualifierLoc.getSourceRange()),
1003                      new (allocator()) syntax::NestedNameSpecifier,
1004                      QualifierLoc);
1005     return true;
1006   }
1007 
1008   syntax::IdExpression *buildIdExpression(NestedNameSpecifierLoc QualifierLoc,
1009                                           SourceLocation TemplateKeywordLoc,
1010                                           SourceRange UnqualifiedIdLoc,
1011                                           ASTPtr From) {
1012     if (QualifierLoc) {
1013       Builder.markChild(QualifierLoc, syntax::NodeRole::Qualifier);
1014       if (TemplateKeywordLoc.isValid())
1015         Builder.markChildToken(TemplateKeywordLoc,
1016                                syntax::NodeRole::TemplateKeyword);
1017     }
1018 
1019     auto *TheUnqualifiedId = new (allocator()) syntax::UnqualifiedId;
1020     Builder.foldNode(Builder.getRange(UnqualifiedIdLoc), TheUnqualifiedId,
1021                      nullptr);
1022     Builder.markChild(TheUnqualifiedId, syntax::NodeRole::UnqualifiedId);
1023 
1024     auto IdExpressionBeginLoc =
1025         QualifierLoc ? QualifierLoc.getBeginLoc() : UnqualifiedIdLoc.getBegin();
1026 
1027     auto *TheIdExpression = new (allocator()) syntax::IdExpression;
1028     Builder.foldNode(
1029         Builder.getRange(IdExpressionBeginLoc, UnqualifiedIdLoc.getEnd()),
1030         TheIdExpression, From);
1031 
1032     return TheIdExpression;
1033   }
1034 
1035   bool WalkUpFromMemberExpr(MemberExpr *S) {
1036     // For `MemberExpr` with implicit `this->` we generate a simple
1037     // `id-expression` syntax node, beacuse an implicit `member-expression` is
1038     // syntactically undistinguishable from an `id-expression`
1039     if (S->isImplicitAccess()) {
1040       buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),
1041                         SourceRange(S->getMemberLoc(), S->getEndLoc()), S);
1042       return true;
1043     }
1044 
1045     auto *TheIdExpression = buildIdExpression(
1046         S->getQualifierLoc(), S->getTemplateKeywordLoc(),
1047         SourceRange(S->getMemberLoc(), S->getEndLoc()), nullptr);
1048 
1049     Builder.markChild(TheIdExpression, syntax::NodeRole::Member);
1050 
1051     Builder.markExprChild(S->getBase(), syntax::NodeRole::Object);
1052     Builder.markChildToken(S->getOperatorLoc(), syntax::NodeRole::AccessToken);
1053 
1054     Builder.foldNode(Builder.getExprRange(S),
1055                      new (allocator()) syntax::MemberExpression, S);
1056     return true;
1057   }
1058 
1059   bool WalkUpFromDeclRefExpr(DeclRefExpr *S) {
1060     buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),
1061                       SourceRange(S->getLocation(), S->getEndLoc()), S);
1062 
1063     return true;
1064   }
1065 
1066   // Same logic as DeclRefExpr.
1067   bool WalkUpFromDependentScopeDeclRefExpr(DependentScopeDeclRefExpr *S) {
1068     buildIdExpression(S->getQualifierLoc(), S->getTemplateKeywordLoc(),
1069                       SourceRange(S->getLocation(), S->getEndLoc()), S);
1070 
1071     return true;
1072   }
1073 
1074   bool WalkUpFromCXXThisExpr(CXXThisExpr *S) {
1075     if (!S->isImplicit()) {
1076       Builder.markChildToken(S->getLocation(),
1077                              syntax::NodeRole::IntroducerKeyword);
1078       Builder.foldNode(Builder.getExprRange(S),
1079                        new (allocator()) syntax::ThisExpression, S);
1080     }
1081     return true;
1082   }
1083 
1084   bool WalkUpFromParenExpr(ParenExpr *S) {
1085     Builder.markChildToken(S->getLParen(), syntax::NodeRole::OpenParen);
1086     Builder.markExprChild(S->getSubExpr(), syntax::NodeRole::SubExpression);
1087     Builder.markChildToken(S->getRParen(), syntax::NodeRole::CloseParen);
1088     Builder.foldNode(Builder.getExprRange(S),
1089                      new (allocator()) syntax::ParenExpression, S);
1090     return true;
1091   }
1092 
1093   bool WalkUpFromIntegerLiteral(IntegerLiteral *S) {
1094     Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1095     Builder.foldNode(Builder.getExprRange(S),
1096                      new (allocator()) syntax::IntegerLiteralExpression, S);
1097     return true;
1098   }
1099 
1100   bool WalkUpFromCharacterLiteral(CharacterLiteral *S) {
1101     Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1102     Builder.foldNode(Builder.getExprRange(S),
1103                      new (allocator()) syntax::CharacterLiteralExpression, S);
1104     return true;
1105   }
1106 
1107   bool WalkUpFromFloatingLiteral(FloatingLiteral *S) {
1108     Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1109     Builder.foldNode(Builder.getExprRange(S),
1110                      new (allocator()) syntax::FloatingLiteralExpression, S);
1111     return true;
1112   }
1113 
1114   bool WalkUpFromStringLiteral(StringLiteral *S) {
1115     Builder.markChildToken(S->getBeginLoc(), syntax::NodeRole::LiteralToken);
1116     Builder.foldNode(Builder.getExprRange(S),
1117                      new (allocator()) syntax::StringLiteralExpression, S);
1118     return true;
1119   }
1120 
1121   bool WalkUpFromCXXBoolLiteralExpr(CXXBoolLiteralExpr *S) {
1122     Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1123     Builder.foldNode(Builder.getExprRange(S),
1124                      new (allocator()) syntax::BoolLiteralExpression, S);
1125     return true;
1126   }
1127 
1128   bool WalkUpFromCXXNullPtrLiteralExpr(CXXNullPtrLiteralExpr *S) {
1129     Builder.markChildToken(S->getLocation(), syntax::NodeRole::LiteralToken);
1130     Builder.foldNode(Builder.getExprRange(S),
1131                      new (allocator()) syntax::CxxNullPtrExpression, S);
1132     return true;
1133   }
1134 
1135   bool WalkUpFromUnaryOperator(UnaryOperator *S) {
1136     Builder.markChildToken(S->getOperatorLoc(),
1137                            syntax::NodeRole::OperatorToken);
1138     Builder.markExprChild(S->getSubExpr(), syntax::NodeRole::Operand);
1139 
1140     if (S->isPostfix())
1141       Builder.foldNode(Builder.getExprRange(S),
1142                        new (allocator()) syntax::PostfixUnaryOperatorExpression,
1143                        S);
1144     else
1145       Builder.foldNode(Builder.getExprRange(S),
1146                        new (allocator()) syntax::PrefixUnaryOperatorExpression,
1147                        S);
1148 
1149     return true;
1150   }
1151 
1152   bool WalkUpFromBinaryOperator(BinaryOperator *S) {
1153     Builder.markExprChild(S->getLHS(), syntax::NodeRole::LeftHandSide);
1154     Builder.markChildToken(S->getOperatorLoc(),
1155                            syntax::NodeRole::OperatorToken);
1156     Builder.markExprChild(S->getRHS(), syntax::NodeRole::RightHandSide);
1157     Builder.foldNode(Builder.getExprRange(S),
1158                      new (allocator()) syntax::BinaryOperatorExpression, S);
1159     return true;
1160   }
1161 
1162   /// Builds `CallArguments` syntax node from arguments that appear in source
1163   /// code, i.e. not default arguments.
1164   syntax::CallArguments *
1165   buildCallArguments(CallExpr::arg_range ArgsAndDefaultArgs) {
1166     auto Args = dropDefaultArgs(ArgsAndDefaultArgs);
1167     for (auto *Arg : Args) {
1168       Builder.markExprChild(Arg, syntax::NodeRole::ListElement);
1169       const auto *DelimiterToken =
1170           std::next(Builder.findToken(Arg->getEndLoc()));
1171       if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1172         Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1173     }
1174 
1175     auto *Arguments = new (allocator()) syntax::CallArguments;
1176     if (!Args.empty())
1177       Builder.foldNode(Builder.getRange((*Args.begin())->getBeginLoc(),
1178                                         (*(Args.end() - 1))->getEndLoc()),
1179                        Arguments, nullptr);
1180 
1181     return Arguments;
1182   }
1183 
1184   bool WalkUpFromCallExpr(CallExpr *S) {
1185     Builder.markExprChild(S->getCallee(), syntax::NodeRole::Callee);
1186 
1187     const auto *LParenToken =
1188         std::next(Builder.findToken(S->getCallee()->getEndLoc()));
1189     // FIXME: Assert that `LParenToken` is indeed a `l_paren` once we have fixed
1190     // the test on decltype desctructors.
1191     if (LParenToken->kind() == clang::tok::l_paren)
1192       Builder.markChildToken(LParenToken, syntax::NodeRole::OpenParen);
1193 
1194     Builder.markChild(buildCallArguments(S->arguments()),
1195                       syntax::NodeRole::Arguments);
1196 
1197     Builder.markChildToken(S->getRParenLoc(), syntax::NodeRole::CloseParen);
1198 
1199     Builder.foldNode(Builder.getRange(S->getSourceRange()),
1200                      new (allocator()) syntax::CallExpression, S);
1201     return true;
1202   }
1203 
1204   bool WalkUpFromCXXConstructExpr(CXXConstructExpr *S) {
1205     // Ignore the implicit calls to default constructors.
1206     if ((S->getNumArgs() == 0 || isa<CXXDefaultArgExpr>(S->getArg(0))) &&
1207         S->getParenOrBraceRange().isInvalid())
1208       return true;
1209     return RecursiveASTVisitor::WalkUpFromCXXConstructExpr(S);
1210   }
1211 
1212   bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *S) {
1213     // To construct a syntax tree of the same shape for calls to built-in and
1214     // user-defined operators, ignore the `DeclRefExpr` that refers to the
1215     // operator and treat it as a simple token. Do that by traversing
1216     // arguments instead of children.
1217     for (auto *child : S->arguments()) {
1218       // A postfix unary operator is declared as taking two operands. The
1219       // second operand is used to distinguish from its prefix counterpart. In
1220       // the semantic AST this "phantom" operand is represented as a
1221       // `IntegerLiteral` with invalid `SourceLocation`. We skip visiting this
1222       // operand because it does not correspond to anything written in source
1223       // code.
1224       if (child->getSourceRange().isInvalid()) {
1225         assert(getOperatorNodeKind(*S) ==
1226                syntax::NodeKind::PostfixUnaryOperatorExpression);
1227         continue;
1228       }
1229       if (!TraverseStmt(child))
1230         return false;
1231     }
1232     return WalkUpFromCXXOperatorCallExpr(S);
1233   }
1234 
1235   bool WalkUpFromCXXOperatorCallExpr(CXXOperatorCallExpr *S) {
1236     switch (getOperatorNodeKind(*S)) {
1237     case syntax::NodeKind::BinaryOperatorExpression:
1238       Builder.markExprChild(S->getArg(0), syntax::NodeRole::LeftHandSide);
1239       Builder.markChildToken(S->getOperatorLoc(),
1240                              syntax::NodeRole::OperatorToken);
1241       Builder.markExprChild(S->getArg(1), syntax::NodeRole::RightHandSide);
1242       Builder.foldNode(Builder.getExprRange(S),
1243                        new (allocator()) syntax::BinaryOperatorExpression, S);
1244       return true;
1245     case syntax::NodeKind::PrefixUnaryOperatorExpression:
1246       Builder.markChildToken(S->getOperatorLoc(),
1247                              syntax::NodeRole::OperatorToken);
1248       Builder.markExprChild(S->getArg(0), syntax::NodeRole::Operand);
1249       Builder.foldNode(Builder.getExprRange(S),
1250                        new (allocator()) syntax::PrefixUnaryOperatorExpression,
1251                        S);
1252       return true;
1253     case syntax::NodeKind::PostfixUnaryOperatorExpression:
1254       Builder.markChildToken(S->getOperatorLoc(),
1255                              syntax::NodeRole::OperatorToken);
1256       Builder.markExprChild(S->getArg(0), syntax::NodeRole::Operand);
1257       Builder.foldNode(Builder.getExprRange(S),
1258                        new (allocator()) syntax::PostfixUnaryOperatorExpression,
1259                        S);
1260       return true;
1261     case syntax::NodeKind::CallExpression: {
1262       Builder.markExprChild(S->getArg(0), syntax::NodeRole::Callee);
1263 
1264       const auto *LParenToken =
1265           std::next(Builder.findToken(S->getArg(0)->getEndLoc()));
1266       // FIXME: Assert that `LParenToken` is indeed a `l_paren` once we have
1267       // fixed the test on decltype desctructors.
1268       if (LParenToken->kind() == clang::tok::l_paren)
1269         Builder.markChildToken(LParenToken, syntax::NodeRole::OpenParen);
1270 
1271       Builder.markChild(buildCallArguments(CallExpr::arg_range(
1272                             S->arg_begin() + 1, S->arg_end())),
1273                         syntax::NodeRole::Arguments);
1274 
1275       Builder.markChildToken(S->getRParenLoc(), syntax::NodeRole::CloseParen);
1276 
1277       Builder.foldNode(Builder.getRange(S->getSourceRange()),
1278                        new (allocator()) syntax::CallExpression, S);
1279       return true;
1280     }
1281     case syntax::NodeKind::UnknownExpression:
1282       return WalkUpFromExpr(S);
1283     default:
1284       llvm_unreachable("getOperatorNodeKind() does not return this value");
1285     }
1286   }
1287 
1288   bool WalkUpFromCXXDefaultArgExpr(CXXDefaultArgExpr *S) { return true; }
1289 
1290   bool WalkUpFromNamespaceDecl(NamespaceDecl *S) {
1291     auto Tokens = Builder.getDeclarationRange(S);
1292     if (Tokens.front().kind() == tok::coloncolon) {
1293       // Handle nested namespace definitions. Those start at '::' token, e.g.
1294       // namespace a^::b {}
1295       // FIXME: build corresponding nodes for the name of this namespace.
1296       return true;
1297     }
1298     Builder.foldNode(Tokens, new (allocator()) syntax::NamespaceDefinition, S);
1299     return true;
1300   }
1301 
1302   // FIXME: Deleting the `TraverseParenTypeLoc` override doesn't change test
1303   // results. Find test coverage or remove it.
1304   bool TraverseParenTypeLoc(ParenTypeLoc L) {
1305     // We reverse order of traversal to get the proper syntax structure.
1306     if (!WalkUpFromParenTypeLoc(L))
1307       return false;
1308     return TraverseTypeLoc(L.getInnerLoc());
1309   }
1310 
1311   bool WalkUpFromParenTypeLoc(ParenTypeLoc L) {
1312     Builder.markChildToken(L.getLParenLoc(), syntax::NodeRole::OpenParen);
1313     Builder.markChildToken(L.getRParenLoc(), syntax::NodeRole::CloseParen);
1314     Builder.foldNode(Builder.getRange(L.getLParenLoc(), L.getRParenLoc()),
1315                      new (allocator()) syntax::ParenDeclarator, L);
1316     return true;
1317   }
1318 
1319   // Declarator chunks, they are produced by type locs and some clang::Decls.
1320   bool WalkUpFromArrayTypeLoc(ArrayTypeLoc L) {
1321     Builder.markChildToken(L.getLBracketLoc(), syntax::NodeRole::OpenParen);
1322     Builder.markExprChild(L.getSizeExpr(), syntax::NodeRole::Size);
1323     Builder.markChildToken(L.getRBracketLoc(), syntax::NodeRole::CloseParen);
1324     Builder.foldNode(Builder.getRange(L.getLBracketLoc(), L.getRBracketLoc()),
1325                      new (allocator()) syntax::ArraySubscript, L);
1326     return true;
1327   }
1328 
1329   syntax::ParameterDeclarationList *
1330   buildParameterDeclarationList(ArrayRef<ParmVarDecl *> Params) {
1331     for (auto *P : Params) {
1332       Builder.markChild(P, syntax::NodeRole::ListElement);
1333       const auto *DelimiterToken = std::next(Builder.findToken(P->getEndLoc()));
1334       if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1335         Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1336     }
1337     auto *Parameters = new (allocator()) syntax::ParameterDeclarationList;
1338     if (!Params.empty())
1339       Builder.foldNode(Builder.getRange(Params.front()->getBeginLoc(),
1340                                         Params.back()->getEndLoc()),
1341                        Parameters, nullptr);
1342     return Parameters;
1343   }
1344 
1345   bool WalkUpFromFunctionTypeLoc(FunctionTypeLoc L) {
1346     Builder.markChildToken(L.getLParenLoc(), syntax::NodeRole::OpenParen);
1347 
1348     Builder.markChild(buildParameterDeclarationList(L.getParams()),
1349                       syntax::NodeRole::Parameters);
1350 
1351     Builder.markChildToken(L.getRParenLoc(), syntax::NodeRole::CloseParen);
1352     Builder.foldNode(Builder.getRange(L.getLParenLoc(), L.getEndLoc()),
1353                      new (allocator()) syntax::ParametersAndQualifiers, L);
1354     return true;
1355   }
1356 
1357   bool WalkUpFromFunctionProtoTypeLoc(FunctionProtoTypeLoc L) {
1358     if (!L.getTypePtr()->hasTrailingReturn())
1359       return WalkUpFromFunctionTypeLoc(L);
1360 
1361     auto *TrailingReturnTokens = buildTrailingReturn(L);
1362     // Finish building the node for parameters.
1363     Builder.markChild(TrailingReturnTokens, syntax::NodeRole::TrailingReturn);
1364     return WalkUpFromFunctionTypeLoc(L);
1365   }
1366 
1367   bool TraverseMemberPointerTypeLoc(MemberPointerTypeLoc L) {
1368     // In the source code "void (Y::*mp)()" `MemberPointerTypeLoc` corresponds
1369     // to "Y::*" but it points to a `ParenTypeLoc` that corresponds to
1370     // "(Y::*mp)" We thus reverse the order of traversal to get the proper
1371     // syntax structure.
1372     if (!WalkUpFromMemberPointerTypeLoc(L))
1373       return false;
1374     return TraverseTypeLoc(L.getPointeeLoc());
1375   }
1376 
1377   bool WalkUpFromMemberPointerTypeLoc(MemberPointerTypeLoc L) {
1378     auto SR = L.getLocalSourceRange();
1379     Builder.foldNode(Builder.getRange(SR),
1380                      new (allocator()) syntax::MemberPointer, L);
1381     return true;
1382   }
1383 
1384   // The code below is very regular, it could even be generated with some
1385   // preprocessor magic. We merely assign roles to the corresponding children
1386   // and fold resulting nodes.
1387   bool WalkUpFromDeclStmt(DeclStmt *S) {
1388     Builder.foldNode(Builder.getStmtRange(S),
1389                      new (allocator()) syntax::DeclarationStatement, S);
1390     return true;
1391   }
1392 
1393   bool WalkUpFromNullStmt(NullStmt *S) {
1394     Builder.foldNode(Builder.getStmtRange(S),
1395                      new (allocator()) syntax::EmptyStatement, S);
1396     return true;
1397   }
1398 
1399   bool WalkUpFromSwitchStmt(SwitchStmt *S) {
1400     Builder.markChildToken(S->getSwitchLoc(),
1401                            syntax::NodeRole::IntroducerKeyword);
1402     Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
1403     Builder.foldNode(Builder.getStmtRange(S),
1404                      new (allocator()) syntax::SwitchStatement, S);
1405     return true;
1406   }
1407 
1408   bool WalkUpFromCaseStmt(CaseStmt *S) {
1409     Builder.markChildToken(S->getKeywordLoc(),
1410                            syntax::NodeRole::IntroducerKeyword);
1411     Builder.markExprChild(S->getLHS(), syntax::NodeRole::CaseValue);
1412     Builder.markStmtChild(S->getSubStmt(), syntax::NodeRole::BodyStatement);
1413     Builder.foldNode(Builder.getStmtRange(S),
1414                      new (allocator()) syntax::CaseStatement, S);
1415     return true;
1416   }
1417 
1418   bool WalkUpFromDefaultStmt(DefaultStmt *S) {
1419     Builder.markChildToken(S->getKeywordLoc(),
1420                            syntax::NodeRole::IntroducerKeyword);
1421     Builder.markStmtChild(S->getSubStmt(), syntax::NodeRole::BodyStatement);
1422     Builder.foldNode(Builder.getStmtRange(S),
1423                      new (allocator()) syntax::DefaultStatement, S);
1424     return true;
1425   }
1426 
1427   bool WalkUpFromIfStmt(IfStmt *S) {
1428     Builder.markChildToken(S->getIfLoc(), syntax::NodeRole::IntroducerKeyword);
1429     Builder.markStmtChild(S->getThen(), syntax::NodeRole::ThenStatement);
1430     Builder.markChildToken(S->getElseLoc(), syntax::NodeRole::ElseKeyword);
1431     Builder.markStmtChild(S->getElse(), syntax::NodeRole::ElseStatement);
1432     Builder.foldNode(Builder.getStmtRange(S),
1433                      new (allocator()) syntax::IfStatement, S);
1434     return true;
1435   }
1436 
1437   bool WalkUpFromForStmt(ForStmt *S) {
1438     Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);
1439     Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
1440     Builder.foldNode(Builder.getStmtRange(S),
1441                      new (allocator()) syntax::ForStatement, S);
1442     return true;
1443   }
1444 
1445   bool WalkUpFromWhileStmt(WhileStmt *S) {
1446     Builder.markChildToken(S->getWhileLoc(),
1447                            syntax::NodeRole::IntroducerKeyword);
1448     Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
1449     Builder.foldNode(Builder.getStmtRange(S),
1450                      new (allocator()) syntax::WhileStatement, S);
1451     return true;
1452   }
1453 
1454   bool WalkUpFromContinueStmt(ContinueStmt *S) {
1455     Builder.markChildToken(S->getContinueLoc(),
1456                            syntax::NodeRole::IntroducerKeyword);
1457     Builder.foldNode(Builder.getStmtRange(S),
1458                      new (allocator()) syntax::ContinueStatement, S);
1459     return true;
1460   }
1461 
1462   bool WalkUpFromBreakStmt(BreakStmt *S) {
1463     Builder.markChildToken(S->getBreakLoc(),
1464                            syntax::NodeRole::IntroducerKeyword);
1465     Builder.foldNode(Builder.getStmtRange(S),
1466                      new (allocator()) syntax::BreakStatement, S);
1467     return true;
1468   }
1469 
1470   bool WalkUpFromReturnStmt(ReturnStmt *S) {
1471     Builder.markChildToken(S->getReturnLoc(),
1472                            syntax::NodeRole::IntroducerKeyword);
1473     Builder.markExprChild(S->getRetValue(), syntax::NodeRole::ReturnValue);
1474     Builder.foldNode(Builder.getStmtRange(S),
1475                      new (allocator()) syntax::ReturnStatement, S);
1476     return true;
1477   }
1478 
1479   bool WalkUpFromCXXForRangeStmt(CXXForRangeStmt *S) {
1480     Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);
1481     Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
1482     Builder.foldNode(Builder.getStmtRange(S),
1483                      new (allocator()) syntax::RangeBasedForStatement, S);
1484     return true;
1485   }
1486 
1487   bool WalkUpFromEmptyDecl(EmptyDecl *S) {
1488     Builder.foldNode(Builder.getDeclarationRange(S),
1489                      new (allocator()) syntax::EmptyDeclaration, S);
1490     return true;
1491   }
1492 
1493   bool WalkUpFromStaticAssertDecl(StaticAssertDecl *S) {
1494     Builder.markExprChild(S->getAssertExpr(), syntax::NodeRole::Condition);
1495     Builder.markExprChild(S->getMessage(), syntax::NodeRole::Message);
1496     Builder.foldNode(Builder.getDeclarationRange(S),
1497                      new (allocator()) syntax::StaticAssertDeclaration, S);
1498     return true;
1499   }
1500 
1501   bool WalkUpFromLinkageSpecDecl(LinkageSpecDecl *S) {
1502     Builder.foldNode(Builder.getDeclarationRange(S),
1503                      new (allocator()) syntax::LinkageSpecificationDeclaration,
1504                      S);
1505     return true;
1506   }
1507 
1508   bool WalkUpFromNamespaceAliasDecl(NamespaceAliasDecl *S) {
1509     Builder.foldNode(Builder.getDeclarationRange(S),
1510                      new (allocator()) syntax::NamespaceAliasDefinition, S);
1511     return true;
1512   }
1513 
1514   bool WalkUpFromUsingDirectiveDecl(UsingDirectiveDecl *S) {
1515     Builder.foldNode(Builder.getDeclarationRange(S),
1516                      new (allocator()) syntax::UsingNamespaceDirective, S);
1517     return true;
1518   }
1519 
1520   bool WalkUpFromUsingDecl(UsingDecl *S) {
1521     Builder.foldNode(Builder.getDeclarationRange(S),
1522                      new (allocator()) syntax::UsingDeclaration, S);
1523     return true;
1524   }
1525 
1526   bool WalkUpFromUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *S) {
1527     Builder.foldNode(Builder.getDeclarationRange(S),
1528                      new (allocator()) syntax::UsingDeclaration, S);
1529     return true;
1530   }
1531 
1532   bool WalkUpFromUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *S) {
1533     Builder.foldNode(Builder.getDeclarationRange(S),
1534                      new (allocator()) syntax::UsingDeclaration, S);
1535     return true;
1536   }
1537 
1538   bool WalkUpFromTypeAliasDecl(TypeAliasDecl *S) {
1539     Builder.foldNode(Builder.getDeclarationRange(S),
1540                      new (allocator()) syntax::TypeAliasDeclaration, S);
1541     return true;
1542   }
1543 
1544 private:
1545   /// Folds SimpleDeclarator node (if present) and in case this is the last
1546   /// declarator in the chain it also folds SimpleDeclaration node.
1547   template <class T> bool processDeclaratorAndDeclaration(T *D) {
1548     auto Range = getDeclaratorRange(
1549         Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
1550         getQualifiedNameStart(D), getInitializerRange(D));
1551 
1552     // There doesn't have to be a declarator (e.g. `void foo(int)` only has
1553     // declaration, but no declarator).
1554     if (!Range.getBegin().isValid()) {
1555       Builder.markChild(new (allocator()) syntax::DeclaratorList,
1556                         syntax::NodeRole::Declarators);
1557       Builder.foldNode(Builder.getDeclarationRange(D),
1558                        new (allocator()) syntax::SimpleDeclaration, D);
1559       return true;
1560     }
1561 
1562     auto *N = new (allocator()) syntax::SimpleDeclarator;
1563     Builder.foldNode(Builder.getRange(Range), N, nullptr);
1564     Builder.markChild(N, syntax::NodeRole::ListElement);
1565 
1566     if (!Builder.isResponsibleForCreatingDeclaration(D)) {
1567       // If this is not the last declarator in the declaration we expect a
1568       // delimiter after it.
1569       const auto *DelimiterToken = std::next(Builder.findToken(Range.getEnd()));
1570       if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
1571         Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
1572     } else {
1573       auto *DL = new (allocator()) syntax::DeclaratorList;
1574       auto DeclarationRange = Builder.getDeclarationRange(D);
1575       Builder.foldList(DeclarationRange, DL, nullptr);
1576 
1577       Builder.markChild(DL, syntax::NodeRole::Declarators);
1578       Builder.foldNode(DeclarationRange,
1579                        new (allocator()) syntax::SimpleDeclaration, D);
1580     }
1581     return true;
1582   }
1583 
1584   /// Returns the range of the built node.
1585   syntax::TrailingReturnType *buildTrailingReturn(FunctionProtoTypeLoc L) {
1586     assert(L.getTypePtr()->hasTrailingReturn());
1587 
1588     auto ReturnedType = L.getReturnLoc();
1589     // Build node for the declarator, if any.
1590     auto ReturnDeclaratorRange = SourceRange(GetStartLoc().Visit(ReturnedType),
1591                                              ReturnedType.getEndLoc());
1592     syntax::SimpleDeclarator *ReturnDeclarator = nullptr;
1593     if (ReturnDeclaratorRange.isValid()) {
1594       ReturnDeclarator = new (allocator()) syntax::SimpleDeclarator;
1595       Builder.foldNode(Builder.getRange(ReturnDeclaratorRange),
1596                        ReturnDeclarator, nullptr);
1597     }
1598 
1599     // Build node for trailing return type.
1600     auto Return = Builder.getRange(ReturnedType.getSourceRange());
1601     const auto *Arrow = Return.begin() - 1;
1602     assert(Arrow->kind() == tok::arrow);
1603     auto Tokens = llvm::makeArrayRef(Arrow, Return.end());
1604     Builder.markChildToken(Arrow, syntax::NodeRole::ArrowToken);
1605     if (ReturnDeclarator)
1606       Builder.markChild(ReturnDeclarator, syntax::NodeRole::Declarator);
1607     auto *R = new (allocator()) syntax::TrailingReturnType;
1608     Builder.foldNode(Tokens, R, L);
1609     return R;
1610   }
1611 
1612   void foldExplicitTemplateInstantiation(
1613       ArrayRef<syntax::Token> Range, const syntax::Token *ExternKW,
1614       const syntax::Token *TemplateKW,
1615       syntax::SimpleDeclaration *InnerDeclaration, Decl *From) {
1616     assert(!ExternKW || ExternKW->kind() == tok::kw_extern);
1617     assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
1618     Builder.markChildToken(ExternKW, syntax::NodeRole::ExternKeyword);
1619     Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);
1620     Builder.markChild(InnerDeclaration, syntax::NodeRole::Declaration);
1621     Builder.foldNode(
1622         Range, new (allocator()) syntax::ExplicitTemplateInstantiation, From);
1623   }
1624 
1625   syntax::TemplateDeclaration *foldTemplateDeclaration(
1626       ArrayRef<syntax::Token> Range, const syntax::Token *TemplateKW,
1627       ArrayRef<syntax::Token> TemplatedDeclaration, Decl *From) {
1628     assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
1629     Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);
1630 
1631     auto *N = new (allocator()) syntax::TemplateDeclaration;
1632     Builder.foldNode(Range, N, From);
1633     Builder.markChild(N, syntax::NodeRole::Declaration);
1634     return N;
1635   }
1636 
1637   /// A small helper to save some typing.
1638   llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }
1639 
1640   syntax::TreeBuilder &Builder;
1641   const ASTContext &Context;
1642 };
1643 } // namespace
1644 
1645 void syntax::TreeBuilder::noticeDeclWithoutSemicolon(Decl *D) {
1646   DeclsWithoutSemicolons.insert(D);
1647 }
1648 
1649 void syntax::TreeBuilder::markChildToken(SourceLocation Loc, NodeRole Role) {
1650   if (Loc.isInvalid())
1651     return;
1652   Pending.assignRole(*findToken(Loc), Role);
1653 }
1654 
1655 void syntax::TreeBuilder::markChildToken(const syntax::Token *T, NodeRole R) {
1656   if (!T)
1657     return;
1658   Pending.assignRole(*T, R);
1659 }
1660 
1661 void syntax::TreeBuilder::markChild(syntax::Node *N, NodeRole R) {
1662   assert(N);
1663   setRole(N, R);
1664 }
1665 
1666 void syntax::TreeBuilder::markChild(ASTPtr N, NodeRole R) {
1667   auto *SN = Mapping.find(N);
1668   assert(SN != nullptr);
1669   setRole(SN, R);
1670 }
1671 void syntax::TreeBuilder::markChild(NestedNameSpecifierLoc NNSLoc, NodeRole R) {
1672   auto *SN = Mapping.find(NNSLoc);
1673   assert(SN != nullptr);
1674   setRole(SN, R);
1675 }
1676 
1677 void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
1678   if (!Child)
1679     return;
1680 
1681   syntax::Tree *ChildNode;
1682   if (Expr *ChildExpr = dyn_cast<Expr>(Child)) {
1683     // This is an expression in a statement position, consume the trailing
1684     // semicolon and form an 'ExpressionStatement' node.
1685     markExprChild(ChildExpr, NodeRole::Expression);
1686     ChildNode = new (allocator()) syntax::ExpressionStatement;
1687     // (!) 'getStmtRange()' ensures this covers a trailing semicolon.
1688     Pending.foldChildren(Arena, getStmtRange(Child), ChildNode);
1689   } else {
1690     ChildNode = Mapping.find(Child);
1691   }
1692   assert(ChildNode != nullptr);
1693   setRole(ChildNode, Role);
1694 }
1695 
1696 void syntax::TreeBuilder::markExprChild(Expr *Child, NodeRole Role) {
1697   if (!Child)
1698     return;
1699   Child = IgnoreImplicit(Child);
1700 
1701   syntax::Tree *ChildNode = Mapping.find(Child);
1702   assert(ChildNode != nullptr);
1703   setRole(ChildNode, Role);
1704 }
1705 
1706 const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {
1707   if (L.isInvalid())
1708     return nullptr;
1709   auto It = LocationToToken.find(L);
1710   assert(It != LocationToToken.end());
1711   return It->second;
1712 }
1713 
1714 syntax::TranslationUnit *syntax::buildSyntaxTree(Arena &A,
1715                                                  ASTContext &Context) {
1716   TreeBuilder Builder(A);
1717   BuildTreeVisitor(Context, Builder).TraverseAST(Context);
1718   return std::move(Builder).finalize();
1719 }
1720