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