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