[Syntax] Introduce syntax trees

[ilya-biryukov]

Summary

A tooling-focused alternative to the AST. This commit focuses on the
memory-management strategy and the structure of the AST.

More to follow later:

• Operations to mutate the syntax trees and corresponding textual replacements.
• Mapping between clang AST nodes and syntax tree nodes.
• More node types corresponding to the language constructs.

[sammccall]

clang/include/clang/Tooling/Syntax/Corpus.h

23 ↗

(On Diff #198427)

I think plain SyntaxArena might be a better name here :-/
Corpus refers to texts (the use in dex is by analogy, as we call symbols "documents" from search).

26 ↗

(On Diff #198427)

MainFile is presumably the whole TU, name might need a tweak.
Can it be empty?
The relationship between Corpus and TokenBuffer seems a little weird. Why is it needed?

38 ↗

(On Diff #198427)

Are you planning to have a way to add tokens directly? Having to turn them into text and re-lex them seems like it might be inconvenient.

40 ↗

(On Diff #198427)

Now there's two ways to do this: new (C.allocator()) T(...) or C.construct<T>(...). Do we need both?

(If we do, is the syntax new (C) T(...) more natural?)

clang/include/clang/Tooling/Syntax/Tree.h

35

for a translation unit? or for only decls within the main file?

41

I've been burned with adding these APIs without use cases.

It seems likely you want a way to:

• skip traversal of children
• abort the traversal entirely

clang/include/clang/Tooling/Syntax/Tree/Cascade.h

1 ↗

(On Diff #198427)

this is Cascade.h, not tree.h

1 ↗

(On Diff #198427)

why "cascade"?

1 ↗

(On Diff #198427)

The Tree/ subdirectory seems superfluous - why are these separate from Syntax/?

74 ↗

(On Diff #198427)

This use of "tree node" to mean specifically internal node seems confusing - is it common?

[ilya-biryukov]

clang/include/clang/Tooling/Syntax/Tree.h

41

Not having an option to abort traversal protects us against timing attacks...

Agree with both, will address in this patch.

[ilya-biryukov]

• Make traverse() internal to its only use-site.
• s/Corpus/Arena.
• Address some other comments.

clang/include/clang/Tooling/Syntax/Corpus.h

23 ↗

(On Diff #198427)

Went with Arena

26 ↗

(On Diff #198427)

Operations on the trees sometimes need to know anything about underlying tokens - they have access to TokenBuffer that produced them.

More specifically, this can be used to map between spelled and expanded tokens and check the mappings are possible.

38 ↗

(On Diff #198427)

The tokens have source locations and refer to a text in some buffer. tokenizeBuffer makes is easier, not harder, to mock tokens.

40 ↗

(On Diff #198427)

I think C.construct<T>() read better than new (C) T(...). Not a big fan of placement new exprs.

clang/include/clang/Tooling/Syntax/Tree.h

35

For a translation unit. We will add versions that built for a subtree of the AST later.

41

Removed from the public API, we seem to have different ideas on how it should look like and I'd prefer to focus on storage model in this patch.

clang/include/clang/Tooling/Syntax/Tree/Cascade.h

1 ↗

(On Diff #198427)

Cascade defines a few base nodes: a composite node (TreeNode) and a leaf node that holds tokens.
I'd really like to isolate them from language-specific nodes, so language-specific nodes live in a separate file (Nodes.h).
However, they need to see the definition of a composite node, hence the split.

Users are advised to use an umbrella header, Tree.h. The extra directory is to minimize the number of headers in the top-level directory, having too many is confusing.

74 ↗

(On Diff #198427)

I don't think it's common, can use CompositeNode - seems like a better alternative

[ilya-biryukov]

• s/corpus/arena
• Remove an accidental cmake change

[sammccall]

Definitely like the choice of CompositeNode owning the concrete storage!

clang/include/clang/Tooling/Syntax/Arena.h

1 ↗

(On Diff #198609)

From a user's point of view, this looks a lot like part of the tree structure in some sense.

If you expect that users will need to keep the arena rather than the TokenBuffer around (e.g. so nodes can be allocated), then it might make sense to declare it at the bottom of Cascade.h

clang/include/clang/Tooling/Syntax/Corpus.h

38 ↗

(On Diff #198427)

Fair enough.

lexBuffer might be a slightly clearer name?

Who are the intended non-test users of this function? Are they better served by being able (and responsible) for constructing a MemoryBuffer with e.g. a sensible name and ownership, or would it be better to pass a StringRef and have the Arena come up with a sensible "anonymous" name?

40 ↗

(On Diff #198427)

They are fairly consistently used in llvm/clang for this sort of thing, though.

I find it valuable because arena allocations look otherwise a lot like buggy ownership patterns. The dedicated syntax calls out the unusual case: we're creating a new thing, and someone else owns it, but won't do anything with it.

clang/include/clang/Tooling/Syntax/Tree.h

12

As discussed offline:

• I don't think (at this point) we need an umbrella header. Generic tree structure, specific node semantics, and operations like "build a tree" are distinct enough from a user POV that asking them to include headers is fine.
• We may want an umbrella for the node types, if we end up splitting that, but no need yet.
• Splitting generic tree stuff vs specific node stuff sounds good, but I think having them be sibling headers in Tooling/Syntax is enough - not sure about the Tree/ subdirectory.

So I'd suggest something like:

• Tree/Cascade.h + Arena.h --> Tree.h
• Tree.h -> BuildTree.h
• Tree/Nodes.h + NodeKind.h --> Nodes.h

(have comments on some of these throughout)

clang/include/clang/Tooling/Syntax/Tree/Cascade.h

39 ↗

(On Diff #198609)

maybe add a comment - newly created nodes have no parent until added to one

59 ↗

(On Diff #198609)

syntax::Leaf vs syntax::Struct seems a little odd - it talks about the tree structure rather than the contents. (Unlike TreeNode/CompositeNode this is likely to be used for its specific semantics).

Maybe syntax::Tokens (though the s is subtle). syntax::Text?

64 ↗

(On Diff #198609)

you're going to want classof for each node type, a private copy constructor (for cloning), a friend statement to whatever does the cloning (or the clone() function itself, if it goes on the class...)

You may want to put this behind a DEFINE_NODE_BOILERPLATE(Leaf) macro :-(

1 ↗

(On Diff #198427)

I like the separation - my concern here was the specific word "Cascade".
I'd suggest "Tree" here as it really does define the structure.
The existing "Tree.h" defines operations, and can be named after them. As discussed, I think the design is clean and doesn't need to be hidden by an umbrella header.

74 ↗

(On Diff #198427)

What about Subtree?

clang/include/clang/Tooling/Syntax/Tree/NodeKind.h

1 ↗

(On Diff #198609)

Why is this separate from Nodes.h?

clang/include/clang/Tooling/Syntax/Tree/NodeList.h

1 ↗

(On Diff #198609)

Implementing custom containers is a bit sad.

Alternatives we discussed:

• adapt bumpptrallocactor to std allocator and use std::vector: wastes a pointer from vector->allocator
• use ArrayRef<Node*> or ArrayRef<Node> and require the whole list to be reallocated when children change (but *replacing* children is fine)
• use a linked-list representation instead: Node* Node::NextSibling, CompositeNode::FirstChild. This fits the allocation strategy more nicely. You probably need only single links, and can add an iterator if needed.

[sammccall]

clang/include/clang/Tooling/Syntax/Tree/NodeKind.h

22 ↗

(On Diff #198609)

if you make this operator<<, then it's slightly more flexible I think (llvm::to_string also works).
It's not as fast, but I don't think that matters here?

clang/lib/Tooling/Syntax/BuildFromAST.cpp

1 ↗

(On Diff #198609)

I haven't reviewed this file yet :-)

[ilya-biryukov]

clang/include/clang/Tooling/Syntax/Corpus.h

38 ↗

(On Diff #198427)

The only use-case in my prototype so far is creating token nodes for punctuation nodes, e.g. say you want to create an expr of the form <a>+<b>, where both a and b are existing expressions and you need to synthesize a leaf node for +.
We use this function to synthesize a buffer with the corresponding token.

All the use-cases I can imagine are around synthesizing syntax trees (as opposed to constructing them from the AST).

[ilya-biryukov]

• Address comments

[ilya-biryukov]

I've addressed most of the comments, except the naming ones.
We need a convention for naming the language nodes and names for composite and leaf structural nodes.

For "language" nodes, I suggest we use CompoundStatement, Recovery, TopLevelDeclaration, TemplateArgumentList, TypeTemplateArgument, etc. That is, we spell out the words in full, no shorthands like Stmt or Expr. That would make things a bit more verbose, but hopefully that helps distinguish from clang AST.

For structural nodes, see the relevant comment threads.

clang/include/clang/Tooling/Syntax/Arena.h

1 ↗

(On Diff #198609)

Now part of Tree.h

clang/include/clang/Tooling/Syntax/Corpus.h

38 ↗

(On Diff #198427)

Renamed to lexBuffer. This does not have usages (yet), we can also remove it from this patch if needed.

40 ↗

(On Diff #198427)

Removed in favour of placement new. I guess that also makes it a bit more natural to have separate storage for other nodes that have different lifetime (e.g. use a separate arena).

clang/include/clang/Tooling/Syntax/Tree.h

12

Changed to the proposed header structure, it looks good.
Had to move Leaf::classof and TreeNode::classof into a .cpp, they need a definition of NodeKind. Keeping those in a header file was a micro-optimization anyway, that's probably not too important.

clang/include/clang/Tooling/Syntax/Tree/Cascade.h

74 ↗

(On Diff #198427)

Subtree seems ok, although Composite conveys the meaning better to my taste.

Composite does not seem to work without the node suffix, though, and we probably don't want the suffix in other nodes, so I'm torn on this.

59 ↗

(On Diff #198609)

syntax::Tokens actually looks good, but we should rename the tokens() accessor somehow in that case.
I have only super-generic variants in my head: elements(), items(). Any better ideas?

64 ↗

(On Diff #198609)

I'd avoid using macros. As long as the amount of boilerplate is small, it's not too annoying to write.

And it is small for now, we only have a single constructor and a classof per node, so keeping it explicit in this patch seems ok.

We can revisit if more stuff pops up, but I think we do it without extra boilerplate per node for clone, and hopefully for other things too.

clang/include/clang/Tooling/Syntax/Tree/NodeKind.h

1 ↗

(On Diff #198609)

Not anymore. The original reason was that Tree.h need NodeKind for implementing casts and the implementation was in a header.

22 ↗

(On Diff #198609)

For some reason I thought gdb does not show the enum value names, so I added a named method to simplify debugging.

Turns out it does show the enum names, not just int values, so I'm perfectly happy to the stream output operator.

clang/include/clang/Tooling/Syntax/Tree/NodeList.h

1 ↗

(On Diff #198609)

No more custom containers, explicit tree structure seems to be better.

clang/lib/Tooling/Syntax/BuildFromAST.cpp

1 ↗

(On Diff #198609)

Please do!

[ilya-biryukov]

clang/include/clang/Tooling/Syntax/BuildTree.h

12

This needs an update, will do in the next round!

[sammccall]

In D61637#1527727, @ilya-biryukov wrote:

I've addressed most of the comments, except the naming ones.
We need a convention for naming the language nodes and names for composite and leaf structural nodes.

For "language" nodes, I suggest we use CompoundStatement, Recovery, TopLevelDeclaration, TemplateArgumentList, TypeTemplateArgument, etc. That is, we spell out the words in full, no shorthands like Stmt or Expr. That would make things a bit more verbose, but hopefully that helps distinguish from clang AST.

SGTM.

clang/include/clang/Tooling/Syntax/Tree.h

105

as discussed offline, having a leaf node store a range of tokens (rather than just one) looks attractive now, but as the syntax tree gets more detailed there are relatively few cases where multiple consecutive tokens should really be undifferentiated siblings.

Might be better to bite the bullet now and make leaf hold a single token, so our consecutive token ranges become a linked list. This will also flush out accidental assumptions that only tokens in the same Leaf are adjacent.

Given this, I'm not sure there's a better name than syntax::Leaf. You might consider making it a pointer-like object dereferenceable to Token&.

112

As discussed, I think syntax::Tree might actually be a better name here.

"A Node is either a Tree or a Leaf" is a bit weird, but not too hard to remember I think.

130

(curious: why prepend rather than append?)

clang/lib/Tooling/Syntax/BuildTree.cpp

27

I find "currently processed" a bit vague. "Pending"?

38

maybe formNode, formToken, formRoot()?

38

if syntax nodes strictly nest and we form left-to-right and bottom up, then why are there ever pending nodes that aren't in the range? Is it because we don't aggregate them as early as possible?

(edit: after offline discussion, there are precise invariants here that could be documented and asserted)

42

Particularly in view of having tokens be 1:1 with Leaf, *constructing* the token nodes as part of higher level constructs / as part of recovery seems a little odd.

What if we constructed all the leaf nodes up front, forming a linked list:
int -> a -> = -> 2 -> + -> 2 -> ; -> eof

When you form a node that covers a range, you splice out the nodes in that range, replacing with the new node:

int -> a -> = -> (2 + 2) -> ; -> eof
(int a = (2 + 2)) -> ; -> eof
etc

Then the invariant is you have a forest, the roots form a linked list, and the trees' respective leaves are a left-to-right partition of the input tokens.

I think this would mean:

• no separate vector<RangedNode> data structure (AFAICS we can reuse Node)
• don't have the requirement that the formed node must claim a suffix of the pending nodes, which simplifies the recursive AST visitior

We lose the binary search, but I think tracking the last accessed root (current position) and linear searching left/right will be at least as good in practice, because tree traversal is fundamentally pretty local.

49

any particular reason learnRoot() and root() are different functions?

If learnRoot() returned TranslationUnit*, then we avoid the need for the caller to know about the dependency, it would track the state itself.

56

or NodeForRange

93

So explicitly claiming the primitive tokens, but implicitly claiming the subtrees, seems like a weird mix.
Having both explicit might be nicer:

• It seems somewhat likely we want to record/tag their semantics (maybe in the child itself, or even the low bits of its pointer?), rather than having accessors scan around looking for something likely.
• currently when expected subtrees fail to parse, their tokens get (implicitly) wrapped up in Recovery nodes. They're good targets for heuristic parsing, but this probably means we should record what an unexplained range of tokens is supposed to be for.

Thinking of something like:

builder.expectToken(l_brace, S->getLBracLoc());
builder.expectTree(Statement, S->getBody());
builder.expectToken(r_brace, S->getRBracLoc());

where the builder would react to non-null AST nodes by mapping the associated syntax node, and null AST nodes by trying to heuristically parse the tokens in between LBracLoc and RBracLoc.

But lots of unanswered questions here: body is a list of statements, how does that work? What if LBracLoc or RBracLoc is missing? etc.

94

btw what if LBracLoc or RBracLoc are invalid here due to parser recovery?

136

this function needs some high-level implementation comments

165

why can It not point to a node that spans/is past End?

(edit after offline discussion: it's an important invariant that we're always consuming a suffix of the pending nodes)

227

or It = bsearch(Tokens, [&](const Syntax::Token& L) { return !SM.isBeforeInTranslationUnit(L.location(), TokLoc); })

[ilya-biryukov]

• A leaf node stores a single token
• Restructure code to avoid special-casing leaf nodes

[ilya-biryukov]

This is not 100% ready yet, but wanted to send it out anyway, as I'll be on vacation until Tuesday.

I've addressed most major comments. In particular, TreeBuilder now looks simpler (and more structured) to my taste.
One thing that's missing is adding children in arbitrary order. It won't be too complicated (would require some thought on how to properly create recovery nodes, though). I'd be tempted to land the current implementation as is and allow adding children in arbitrary order in a separate change (alongside more types of nodes), but let me know what you think.

clang/include/clang/Tooling/Syntax/Tree.h

105

Leaf now stores a single token, that actually simplifies things quite a bit, thanks!
I'd avoid making it a pointer-like object, given that nodes are often passed as pointers on their own. Making them a pointer-like object would mean we can get code that does double deferences (Tok = **Leaf).

130

Appending to a linked list is O(n). If we reverse it, traversing left-to-right order is O(n).

130

Append is O(n) in the current representation as it requires walking to the tail of the list.

clang/lib/Tooling/Syntax/BuildTree.cpp

42

I went with a slightly different approach, similar to how parser does it. Please let me know what you think.
The new Forest helper struct ensures the tree structure invariants (all tokens must be covered, nodes must nest properly based on a syntax structure), the rest of the code in tree builder takes care of folding the nodes in a proper order and properly advancing the token stream (it's somewhat similar in the details of how parsers are implemented, except that instead of parsing we actually walk a pre-parsed AST).

It still needs some comments, but I think its intentions should be clear.
Let me know what you think, happy to discuss this offline too.

49

learnRoot is called inside ast visitor when processing TranslationUnitDecl and root() is used to consume the result.

I guess we could just delay learnRoot until consume() is called, shouldn't be a big deal. I'll do this in the next iteration.

94

This will currently break and we should definitely fix this

94

We don't recover from errors properly here, I'd add a FIXME and figure this out later. Does that SG?

The general strategy I would propose is to just skip the tokens (we will return null from the corresponding accessors, etc) and create recovery nodes (RecoveryExpression, etc.) for composite nodes.

[ilya-biryukov]

• Do the renames

[ilya-biryukov]

• A few more renames and docs
• Cleanups and comments
• Reformat the code

[ilya-biryukov]

This is ready for another round now.

clang/lib/Tooling/Syntax/BuildTree.cpp

38

Sorry, missed this comment and went with expectToken() and expectNode(), root is now built on consume(). Can change to form*, not a big deal.

I still need to write good docs about the invariants here, so leaving this open.

49

consume() now builds the root node.

93

That's exactly the design we have one, with a limitation that expect* have to be called in left-to-right and bottom-up manner. Also, you can only build a tree that ends at the tokens that were consumed.

This is actually a reasonable interface to build a tree from an actual parser, but might feel weird for a ast-to-syntax transformation. I need to figure out a way to write good docs about it, but there's a separate comment for that. Marking this as done (although the questions you mentioned at the end are still there)

136

Done. Also renamed it to consumeNode.

The docs are very short, though, might need a revamp for clarity.

165

This is now spelled out in the documentation for foldChildren.

[ilya-biryukov]

Although there are still rough edges, I believe the storage model is agreed upon and we can hopefully address the rest in the follow-ups.

[ilya-biryukov]

• Introduce roles to allow distinguishing the child nodes.
• Remove recovery node, use an unknown role instead.
• TreeBuidler now can consume children at any point, not just suffix nodes.

[ilya-biryukov]

• Remove (outdated) changes to gn files

[ilya-biryukov]

This is now in a pretty good shape, I've incorporated changes after our offline discussions about child roles.
The builder interface is also much richer now, removing a requirement that the tree has to be traversed left-to-right (bottom-up is still required!).

[sammccall]

Nice, let's land this!

clang/include/clang/Tooling/Syntax/Nodes.h

36

I don't think TU is actually a declaration. Is there a reason to consider it one from a syntax POV?

42

I have a slight feeling the EOF token is going to be annoying, e.g. can't just splice stuff in at the end of the list. But not sure if it'll be a big deal, and whether the alternatives are better.

44

we discussed offline - with 256 values, is it possible to come up with a single role enum that would cover all node types?

Advantage would be that certain logic could be generic (e.g. Recovery could be a role for leaves under any Tree, LParen/RParen/MainKeyword could apply to if, while, switch...)

[ilya-biryukov]

• s/TranslationUnitDeclaration/TranslationUnit
• Remove accessor from 'eof', add a FIXME to remove it from the tree altogether

[ilya-biryukov]

clang/include/clang/Tooling/Syntax/Nodes.h

36

It's a declaration in a sense that it has a corresponding instance of clang::Decl that it "introduces", i.e. the clang::TranslationUnitDecl.

But you are right, TranslationUnit is a better name: this aligns with the C++ grammar from the standard (translation-unit), it does lack similarity with other declarations from the standard (and from clang).

Renamed to TranslationUnit

42

That's a good point, I actually don't see how eof token in a tree would be useful (it's probably fine to have in the TokenBuffer, though, allows). Moreover, it could cause confusion and bugs when working with multiple translation units (I imagine moving nodes between two different TUs and ending up with multiple eofs somewhere)

I've removed the corresponding accessor from the TranslationUnit node and added a FIXME to remove it from the tree altogether.

44

Will need to do some estimations to answer this properly, but my gut feeling is that 256 could end up being too limiting in the long run (I would expect each node to have at least one child, so without deduplication we can at least as many roles as we have kinds).

Could imagine a two-level numbering scheme, though:

• some generic roles like lparen, rparen, etc, take first N roles.
• higher numbers are for node-specific roles (e.g. LHS or RHS of a BinaryExpr).

But at that point, we probably don't have the benefits of a single enum.

[RKSimon]

@ilya-biryukov We're seeing buildbot failures in SyntaxTests.exe :
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/50927
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/26822

Failing Tests (1):

Clang-Unit :: Tooling/Syntax/./SyntaxTests.exe/SyntaxTreeTest.Basic

[ilya-biryukov]

In D61637#1575542, @RKSimon wrote:

@ilya-biryukov We're seeing buildbot failures in SyntaxTests.exe :
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/50927
http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/26822

Failing Tests (1):

Clang-Unit :: Tooling/Syntax/./SyntaxTests.exe/SyntaxTreeTest.Basic

Sorry about that. That's the same error we had with the previous patch. Will send a fix right away.

[RKSimon]

@ilya-biryukov I'm sorry but I've reverted this at rL365465

[ilya-biryukov]

Relanded in rL365466 with a fix to the crash.

[sammccall]

clang/include/clang/Tooling/Syntax/Nodes.h

44

I think we misunderstood each other here... I think this is fairly important, and that we'd agreed on it in offline discussion. Didn't mean to leave it as an optional comment.

I'd be very surprised if 256 were too limiting. Indeed most nodes will have children, but most of them will not have unique roles. (And I would be surprised if we have 200 node types, but maybe not that surprised...).

If there's a more fundamental objection to merging these, I'd like to find some agreement before going further.

clang/include/clang/Tooling/Syntax/BuildTree.h

+//===- BuildTree.h - build syntax trees -----------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Functions to construct a syntax tree from an AST.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_H
+#define LLVM_CLANG_TOOLING_SYNTAX_TREE_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Tooling/Syntax/Nodes.h"
+
+namespace clang {
+namespace syntax {
+
+/// Build a syntax tree for the main file.
+syntax::TranslationUnit *buildSyntaxTree(Arena &A,
+                                         const clang::TranslationUnitDecl &TU);
+} // namespace syntax
+} // namespace clang
+#endif

clang/include/clang/Tooling/Syntax/Nodes.h

+//===- Nodes.h - syntax nodes for C/C++ grammar constructs ----*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Syntax tree nodes for C, C++ and Objective-C grammar constructs.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_NODES_H
+#define LLVM_CLANG_TOOLING_SYNTAX_NODES_H
+
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Lex/Token.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "clang/Tooling/Syntax/Tree.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace clang {
+namespace syntax {
+
+/// A kind of a syntax node, used for implementing casts.
+enum class NodeKind : uint16_t {
+  Leaf,
+  TranslationUnit,
+  TopLevelDeclaration,
+  CompoundStatement
+};
+/// For debugging purposes.
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, NodeKind K);
+
+/// A root node for a translation unit. Parent is always null.
+class TranslationUnit final : public Tree {
+public:
+  TranslationUnit() : Tree(NodeKind::TranslationUnit) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::TranslationUnit;
+  }
+};
+
+/// FIXME: this node is temporary and will be replaced with nodes for various
+///        'declarations' and 'declarators' from the C/C++ grammar
+///
+/// Represents any top-level declaration. Only there to give the syntax tree a
+/// bit of structure until we implement syntax nodes for declarations and
+/// declarators.
+class TopLevelDeclaration final : public Tree {
+public:
+  TopLevelDeclaration() : Tree(NodeKind::TopLevelDeclaration) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::TopLevelDeclaration;
+  }
+};
+
+/// An abstract node for C++ statements, e.g. 'while', 'if', etc.
+class Statement : public Tree {
+public:
+  Statement(NodeKind K) : Tree(K) {}
+  static bool classof(const Node *N) {
+    return NodeKind::CompoundStatement <= N->kind() &&
+           N->kind() <= NodeKind::CompoundStatement;
+  }
+};
+
+/// { statement1; statement2; … }
+class CompoundStatement final : public Statement {
+public:
+  CompoundStatement() : Statement(NodeKind::CompoundStatement) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::CompoundStatement;
+  }
+  syntax::Leaf *lbrace();
+  syntax::Leaf *rbrace();
+
+  struct Roles {
+    static constexpr NodeRole lbrace = 1;
+    static constexpr NodeRole rbrace = 2;
+  };
+};
+
+} // namespace syntax
+} // namespace clang
+#endif

clang/include/clang/Tooling/Syntax/Tree.h

+//===- Tree.h - structure of the syntax tree ------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Defines the basic structure of the syntax tree. There are two kinds of nodes:
+//   - leaf nodes correspond to a token in the expanded token stream,
+//   - tree nodes correspond to language grammar constructs.
+//
+// The tree is initially built from an AST. Each node of a newly built tree
+// covers a continous subrange of expanded tokens (i.e. tokens after
+// preprocessing), the specific tokens coverered are stored in the leaf nodes of
+// a tree. A post-order traversal of a tree will visit leaf nodes in an order
+// corresponding the original order of expanded tokens.
+//
+// This is still work in progress and highly experimental, we leave room for
+// ourselves to completely change the design and/or implementation.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_TOOLING_SYNTAX_TREE_CASCADE_H
+#define LLVM_CLANG_TOOLING_SYNTAX_TREE_CASCADE_H
+
+#include "clang/Basic/LangOptions.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Allocator.h"
+#include <cstdint>
+
+namespace clang {
+namespace syntax {
+
+/// A memory arena for syntax trees. Also tracks the underlying token buffers,
+/// source manager, etc.
+class Arena {
+public:
+  Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
+        TokenBuffer Tokens);
+
+  const SourceManager &sourceManager() const { return SourceMgr; }
+  const LangOptions &langOptions() const { return LangOpts; }
+
+  const TokenBuffer &tokenBuffer() const;
+  llvm::BumpPtrAllocator &allocator() { return Allocator; }
+
+  /// Add \p Buffer to the underlying source manager, tokenize it and store the
+  /// resulting tokens. Useful when there is a need to materialize tokens that
+  /// were not written in user code.
+  std::pair<FileID, llvm::ArrayRef<syntax::Token>>
+  lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Buffer);
+
+private:
+  SourceManager &SourceMgr;
+  const LangOptions &LangOpts;
+  TokenBuffer Tokens;
+  /// IDs and storage for additional tokenized files.
+  llvm::DenseMap<FileID, std::vector<syntax::Token>> ExtraTokens;
+  /// Keeps all the allocated nodes and their intermediate data structures.
+  llvm::BumpPtrAllocator Allocator;
+};
+
+class Tree;
+class TreeBuilder;
+enum class NodeKind : uint16_t;
+
+/// Represents a relation of this node to its parent, e.g. 'lbrace inside a
+/// compound statement'.
+///
+/// Each node type defines a set of roles for its children.
+using NodeRole = uint8_t;
+
+/// Role for detached nodes, i.e. the ones that do not have parent nodes.
+constexpr NodeRole NodeRoleDetached = 0;
+/// Role for children of unknown semantic nature, e.g. skipped tokens, comments.
+constexpr NodeRole NodeRoleUnknown = 255;
+
+/// A node in a syntax tree. Each node is either a Leaf (representing tokens) or
+/// a Tree (representing language constructrs).
+class Node {
+public:
+  /// Newly created nodes are detached from a tree, parent and sibling links are
+  /// set when the node is added as a child to another one.
+  Node(NodeKind Kind)
+      : Parent(nullptr), NextSibling(nullptr),
+        Kind(static_cast<unsigned>(Kind)), Role(NodeRoleDetached) {}
+
+  NodeKind kind() const { return static_cast<NodeKind>(Kind); }
+  NodeRole role() const { return Role; }
+
+  const Tree *parent() const { return Parent; }
+  Tree *parent() { return Parent; }
+
+  const Node *nextSibling() const { return NextSibling; }
+  Node *nextSibling() { return NextSibling; }
+
+  /// Dumps the structure of a subtree. For debugging and testing purposes.
+  std::string dump(const Arena &A) const;
+  /// Dumps the tokens forming this subtree.
+  std::string dumpTokens(const Arena &A) const;
+
+private:
+  // Tree is allowed to change the Parent link and Role.
+  friend class Tree;
+
+  Tree *Parent;
+  Node *NextSibling;
+  unsigned Kind : 16;
+  unsigned Role : 8;
+};
+
+/// A leaf node points to a single token inside the expanded token stream.
+class Leaf final : public Node {
+public:
+  Leaf(const syntax::Token *T);
+  static bool classof(const Node *N);
+
+  const syntax::Token *token() const { return Tok; }
+
+private:
+  const syntax::Token *Tok;
+};
+
+/// A node that has children and represents a syntactic language construct.
+class Tree : public Node {
+public:
+  using Node::Node;
+  static bool classof(const Node *N);
+
+  Node *firstChild() { return FirstChild; }
+  const Node *firstChild() const { return FirstChild; }
+
+protected:
+  /// Find the first node with a corresponding role.
+  syntax::Node *findChild(NodeRole R);
+
+private:
+  /// Prepend \p Child to the list of children and and sets the parent pointer.
+  /// A very low-level operation that does not check any invariants, only used
+  /// by TreeBuilder.
+  /// EXPECTS: Role != NodeRoleDetached.
+  void prependChildLowLevel(Node *Child, NodeRole Role);
+  friend class TreeBuilder;
+
+  Node *FirstChild = nullptr;
+};
+
+} // namespace syntax
+} // namespace clang
+
+#endif

clang/lib/Tooling/Syntax/BuildTree.cpp

+//===- BuildTree.cpp ------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/BuildTree.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Lex/Lexer.h"
+#include "clang/Tooling/Syntax/Nodes.h"
+#include "clang/Tooling/Syntax/Tokens.h"
+#include "clang/Tooling/Syntax/Tree.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/raw_ostream.h"
+#include <map>
+
+using namespace clang;
+
+/// A helper class for constructing the syntax tree while traversing a clang
+/// AST.
+///
+/// At each point of the traversal we maintain a list of pending nodes.
+/// Initially all tokens are added as pending nodes. When processing a clang AST
+/// node, the clients need to:
+///   - create a corresponding syntax node,
+///   - assign roles to all pending child nodes with 'markChild' and
+///     'markChildToken',
+///   - replace the child nodes with the new syntax node in the pending list
+///     with 'foldNode'.
+///
+/// Note that all children are expected to be processed when building a node.
+///
+/// Call finalize() to finish building the tree and consume the root node.
+class syntax::TreeBuilder {
+public:
+  TreeBuilder(syntax::Arena &Arena) : Arena(Arena), Pending(Arena) {}
+
+  llvm::BumpPtrAllocator &allocator() { return Arena.allocator(); }
+
+  /// Populate children for \p New node, assuming it covers tokens from \p
+  /// Range.
+  void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New);
+
+  /// Set role for a token starting at \p Loc.
+  void markChildToken(SourceLocation Loc, tok::TokenKind Kind, NodeRole R);
+
+  /// Finish building the tree and consume the root node.
+  syntax::TranslationUnit *finalize() && {
+    auto Tokens = Arena.tokenBuffer().expandedTokens();
+    // Build the root of the tree, consuming all the children.
+    Pending.foldChildren(Tokens,
+                         new (Arena.allocator()) syntax::TranslationUnit);
+
+    return cast<syntax::TranslationUnit>(std::move(Pending).finalize());
+  }
+
+  /// getRange() finds the syntax tokens corresponding to the passed source
+  /// locations.
+  /// \p First is the start position of the first token and \p Last is the start
+  /// position of the last token.
+  llvm::ArrayRef<syntax::Token> getRange(SourceLocation First,
+                                         SourceLocation Last) const {
+    assert(First.isValid());
+    assert(Last.isValid());
+    assert(First == Last ||
+           Arena.sourceManager().isBeforeInTranslationUnit(First, Last));
+    return llvm::makeArrayRef(findToken(First), std::next(findToken(Last)));
+  }
+  llvm::ArrayRef<syntax::Token> getRange(const Decl *D) const {
+    return getRange(D->getBeginLoc(), D->getEndLoc());
+  }
+  llvm::ArrayRef<syntax::Token> getRange(const Stmt *S) const {
+    return getRange(S->getBeginLoc(), S->getEndLoc());
+  }
+
+private:
+  /// Finds a token starting at \p L. The token must exist.
+  const syntax::Token *findToken(SourceLocation L) const;
+
+  /// A collection of trees covering the input tokens.
+  /// When created, each tree corresponds to a single token in the file.
+  /// Clients call 'foldChildren' to attach one or more subtrees to a parent
+  /// node and update the list of trees accordingly.
+  ///
+  /// Ensures that added nodes properly nest and cover the whole token stream.
+  struct Forest {
+    Forest(syntax::Arena &A) {
+      // FIXME: do not add 'eof' to the tree.
+
+      // Create all leaf nodes.
+      for (auto &T : A.tokenBuffer().expandedTokens())
+        Trees.insert(Trees.end(),
+                     {&T, NodeAndRole{new (A.allocator()) syntax::Leaf(&T)}});
+    }
+
+    void assignRole(llvm::ArrayRef<syntax::Token> Range,
+                    syntax::NodeRole Role) {
+      assert(!Range.empty());
+      auto It = Trees.lower_bound(Range.begin());
+      assert(It != Trees.end() && "no node found");
+      assert(It->first == Range.begin() && "no child with the specified range");
+      assert(std::next(It) == Trees.end() ||
+             std::next(It)->first == Range.end() &&
+                 "no child with the specified range");
+      It->second.Role = Role;
+    }
+
+    /// Add \p Node to the forest and fill its children nodes based on the \p
+    /// NodeRange.
+    void foldChildren(llvm::ArrayRef<syntax::Token> NodeTokens,
+                      syntax::Tree *Node) {
+      assert(!NodeTokens.empty());
+      assert(Node->firstChild() == nullptr && "node already has children");
+
+      auto *FirstToken = NodeTokens.begin();
+      auto BeginChildren = Trees.lower_bound(FirstToken);
+      assert(BeginChildren != Trees.end() &&
+             BeginChildren->first == FirstToken &&
+             "fold crosses boundaries of existing subtrees");
+      auto EndChildren = Trees.lower_bound(NodeTokens.end());
+      assert(EndChildren == Trees.end() ||
+             EndChildren->first == NodeTokens.end() &&
+                 "fold crosses boundaries of existing subtrees");
+
+      // (!) we need to go in reverse order, because we can only prepend.
+      for (auto It = EndChildren; It != BeginChildren; --It)
+        Node->prependChildLowLevel(std::prev(It)->second.Node,
+                                   std::prev(It)->second.Role);
+
+      Trees.erase(BeginChildren, EndChildren);
+      Trees.insert({FirstToken, NodeAndRole(Node)});
+    }
+
+    // EXPECTS: all tokens were consumed and are owned by a single root node.
+    syntax::Node *finalize() && {
+      assert(Trees.size() == 1);
+      auto *Root = Trees.begin()->second.Node;
+      Trees = {};
+      return Root;
+    }
+
+    std::string str(const syntax::Arena &A) const {
+      std::string R;
+      for (auto It = Trees.begin(); It != Trees.end(); ++It) {
+        unsigned CoveredTokens =
+            It != Trees.end()
+                ? (std::next(It)->first - It->first)
+                : A.tokenBuffer().expandedTokens().end() - It->first;
+
+        R += llvm::formatv("- '{0}' covers '{1}'+{2} tokens\n",
+                           It->second.Node->kind(),
+                           It->first->text(A.sourceManager()), CoveredTokens);
+        R += It->second.Node->dump(A);
+      }
+      return R;
+    }
+
+  private:
+    /// A with a role that should be assigned to it when adding to a parent.
+    struct NodeAndRole {
+      explicit NodeAndRole(syntax::Node *Node)
+          : Node(Node), Role(NodeRoleUnknown) {}
+
+      syntax::Node *Node;
+      NodeRole Role;
+    };
+
+    /// Maps from the start token to a subtree starting at that token.
+    /// FIXME: storing the end tokens is redundant.
+    /// FIXME: the key of a map is redundant, it is also stored in NodeForRange.
+    std::map<const syntax::Token *, NodeAndRole> Trees;
+  };
+
+  /// For debugging purposes.
+  std::string str() { return Pending.str(Arena); }
+
+  syntax::Arena &Arena;
+  Forest Pending;
+};
+
+namespace {
+class BuildTreeVisitor : public RecursiveASTVisitor<BuildTreeVisitor> {
+public:
+  explicit BuildTreeVisitor(ASTContext &Ctx, syntax::TreeBuilder &Builder)
+      : Builder(Builder), LangOpts(Ctx.getLangOpts()) {}
+
+  bool shouldTraversePostOrder() const { return true; }
+
+  bool TraverseDecl(Decl *D) {
+    if (!D || isa<TranslationUnitDecl>(D))
+      return RecursiveASTVisitor::TraverseDecl(D);
+    if (!llvm::isa<TranslationUnitDecl>(D->getDeclContext()))
+      return true; // Only build top-level decls for now, do not recurse.
+    return RecursiveASTVisitor::TraverseDecl(D);
+  }
+
+  bool VisitDecl(Decl *D) {
+    assert(llvm::isa<TranslationUnitDecl>(D->getDeclContext()) &&
+           "expected a top-level decl");
+    assert(!D->isImplicit());
+    Builder.foldNode(Builder.getRange(D),
+                     new (allocator()) syntax::TopLevelDeclaration());
+    return true;
+  }
+
+  bool WalkUpFromTranslationUnitDecl(TranslationUnitDecl *TU) {
+    // (!) we do not want to call VisitDecl(), the declaration for translation
+    // unit is built by finalize().
+    return true;
+  }
+
+  bool WalkUpFromCompoundStmt(CompoundStmt *S) {
+    using Roles = syntax::CompoundStatement::Roles;
+
+    Builder.markChildToken(S->getLBracLoc(), tok::l_brace, Roles::lbrace);
+    Builder.markChildToken(S->getRBracLoc(), tok::r_brace, Roles::rbrace);
+
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::CompoundStatement);
+    return true;
+  }
+
+private:
+  /// A small helper to save some typing.
+  llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }
+
+  syntax::TreeBuilder &Builder;
+  const LangOptions &LangOpts;
+};
+} // namespace
+
+void syntax::TreeBuilder::foldNode(llvm::ArrayRef<syntax::Token> Range,
+                                   syntax::Tree *New) {
+  Pending.foldChildren(Range, New);
+}
+
+void syntax::TreeBuilder::markChildToken(SourceLocation Loc,
+                                         tok::TokenKind Kind, NodeRole Role) {
+  if (Loc.isInvalid())
+    return;
+  Pending.assignRole(*findToken(Loc), Role);
+}
+
+const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {
+  auto Tokens = Arena.tokenBuffer().expandedTokens();
+  auto &SM = Arena.sourceManager();
+  auto It = llvm::partition_point(Tokens, [&](const syntax::Token &T) {
+    return SM.isBeforeInTranslationUnit(T.location(), L);
+  });
+  assert(It != Tokens.end());
+  assert(It->location() == L);
+  return &*It;
+}
+
+syntax::TranslationUnit *
+syntax::buildSyntaxTree(Arena &A, const TranslationUnitDecl &TU) {
+  TreeBuilder Builder(A);
+  BuildTreeVisitor(TU.getASTContext(), Builder).TraverseAST(TU.getASTContext());
+  return std::move(Builder).finalize();
+}

clang/lib/Tooling/Syntax/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangToolingSyntax
+  BuildTree.cpp
+  Nodes.cpp
   Tokens.cpp
+  Tree.cpp
 
   LINK_LIBS
+  clangAST
   clangBasic
   clangFrontend
   clangLex
+  clangToolingCore
   )

clang/lib/Tooling/Syntax/Nodes.cpp

+//===- Nodes.cpp ----------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/Nodes.h"
+#include "clang/Basic/TokenKinds.h"
+
+using namespace clang;
+
+llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeKind K) {
+  switch (K) {
+  case NodeKind::Leaf:
+    return OS << "Leaf";
+  case NodeKind::TranslationUnit:
+    return OS << "TranslationUnit";
+  case NodeKind::TopLevelDeclaration:
+    return OS << "TopLevelDeclaration";
+  case NodeKind::CompoundStatement:
+    return OS << "CompoundStatement";
+  }
+  llvm_unreachable("unknown node kind");
+}
+
+syntax::Leaf *syntax::CompoundStatement::lbrace() {
+  return llvm::cast_or_null<syntax::Leaf>(findChild(Roles::lbrace));
+}
+
+syntax::Leaf *syntax::CompoundStatement::rbrace() {
+  return llvm::cast_or_null<syntax::Leaf>(findChild(Roles::rbrace));
+}

clang/lib/Tooling/Syntax/Tree.cpp

+//===- Tree.cpp -----------------------------------------------*- C++ -*-=====//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Tooling/Syntax/Tree.h"
+#include "clang/Basic/TokenKinds.h"
+#include "clang/Tooling/Syntax/Nodes.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Casting.h"
+
+using namespace clang;
+
+syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
+                     TokenBuffer Tokens)
+    : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {}
+
+const clang::syntax::TokenBuffer &syntax::Arena::tokenBuffer() const {
+  return Tokens;
+}
+
+std::pair<FileID, llvm::ArrayRef<syntax::Token>>
+syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
+  auto FID = SourceMgr.createFileID(std::move(Input));
+  auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
+  assert(It.second && "duplicate FileID");
+  return {FID, It.first->second};
+}
+
+syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
+  assert(Tok != nullptr);
+}
+
+bool syntax::Leaf::classof(const Node *N) {
+  return N->kind() == NodeKind::Leaf;
+}
+
+bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
+
+void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
+  assert(Child->Parent == nullptr);
+  assert(Child->NextSibling == nullptr);
+  assert(Child->Role == NodeRoleDetached);
+  assert(Role != NodeRoleDetached);
+
+  Child->Parent = this;
+  Child->NextSibling = this->FirstChild;
+  Child->Role = Role;
+  this->FirstChild = Child;
+}
+
+namespace {
+static void traverse(const syntax::Node *N,
+                     llvm::function_ref<void(const syntax::Node *)> Visit) {
+  if (auto *T = dyn_cast<syntax::Tree>(N)) {
+    for (auto *C = T->firstChild(); C; C = C->nextSibling())
+      traverse(C, Visit);
+  }
+  Visit(N);
+}
+static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens,
+                       const SourceManager &SM) {
+  assert(!Tokens.empty());
+  bool First = true;
+  for (const auto &T : Tokens) {
+    if (!First)
+      OS << " ";
+    else
+      First = false;
+    // Handle 'eof' separately, calling text() on it produces an empty string.
+    if (T.kind() == tok::eof) {
+      OS << "<eof>";
+      continue;
+    }
+    OS << T.text(SM);
+  }
+}
+
+static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
+                     const syntax::Arena &A, std::vector<bool> IndentMask) {
+  if (N->role() != syntax::NodeRoleUnknown) {
+    // FIXME: print the symbolic name of a role.
+    if (N->role() == syntax::NodeRoleDetached)
+      OS << "*: ";
+    else
+      OS << static_cast<int>(N->role()) << ": ";
+  }
+  if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
+    dumpTokens(OS, *L->token(), A.sourceManager());
+    OS << "\n";
+    return;
+  }
+
+  auto *T = llvm::cast<syntax::Tree>(N);
+  OS << T->kind() << "\n";
+
+  for (auto It = T->firstChild(); It != nullptr; It = It->nextSibling()) {
+    for (bool Filled : IndentMask) {
+      if (Filled)
+        OS << "| ";
+      else
+        OS << "  ";
+    }
+    if (!It->nextSibling()) {
+      OS << "`-";
+      IndentMask.push_back(false);
+    } else {
+      OS << "|-";
+      IndentMask.push_back(true);
+    }
+    dumpTree(OS, It, A, IndentMask);
+    IndentMask.pop_back();
+  }
+}
+} // namespace
+
+std::string syntax::Node::dump(const Arena &A) const {
+  std::string Str;
+  llvm::raw_string_ostream OS(Str);
+  dumpTree(OS, this, A, /*IndentMask=*/{});
+  return std::move(OS.str());
+}
+
+std::string syntax::Node::dumpTokens(const Arena &A) const {
+  std::string Storage;
+  llvm::raw_string_ostream OS(Storage);
+  traverse(this, [&](const syntax::Node *N) {
+    auto *L = llvm::dyn_cast<syntax::Leaf>(N);
+    if (!L)
+      return;
+    ::dumpTokens(OS, *L->token(), A.sourceManager());
+  });
+  return OS.str();
+}
+
+syntax::Node *syntax::Tree::findChild(NodeRole R) {
+  for (auto *C = FirstChild; C; C = C->nextSibling()) {
+    if (C->Role == R)
+      return C;
+  }
+  return nullptr;
+}

clang/unittests/Tooling/Syntax/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_unittest(SyntaxTests
+  TreeTest.cpp
   TokensTest.cpp
 )
 
 clang_target_link_libraries(SyntaxTests
   PRIVATE
   clangAST
   clangBasic
   clangFrontend

clang/unittests/Tooling/Syntax/TreeTest.cpp

+//===- TreeTest.cpp -------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Tooling/Syntax/Tree.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/Decl.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Frontend/FrontendAction.h"
+#include "clang/Lex/PreprocessorOptions.h"
+#include "clang/Tooling/Syntax/BuildTree.h"
+#include "clang/Tooling/Syntax/Nodes.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <cstdlib>
+
+using namespace clang;
+
+namespace {
+class SyntaxTreeTest : public ::testing::Test {
+protected:
+  // Build a syntax tree for the code.
+  syntax::TranslationUnit *buildTree(llvm::StringRef Code) {
+    // FIXME: this code is almost the identical to the one in TokensTest. Share
+    //        it.
+    class BuildSyntaxTree : public ASTConsumer {
+    public:
+      BuildSyntaxTree(syntax::TranslationUnit *&Root,
+                      std::unique_ptr<syntax::Arena> &Arena,
+                      std::unique_ptr<syntax::TokenCollector> Tokens)
+          : Root(Root), Arena(Arena), Tokens(std::move(Tokens)) {
+        assert(this->Tokens);
+      }
+
+      void HandleTranslationUnit(ASTContext &Ctx) override {
+        Arena = llvm::make_unique<syntax::Arena>(Ctx.getSourceManager(),
+                                                 Ctx.getLangOpts(),
+                                                 std::move(*Tokens).consume());
+        Tokens = nullptr; // make sure we fail if this gets called twice.
+        Root = syntax::buildSyntaxTree(*Arena, *Ctx.getTranslationUnitDecl());
+      }
+
+    private:
+      syntax::TranslationUnit *&Root;
+      std::unique_ptr<syntax::Arena> &Arena;
+      std::unique_ptr<syntax::TokenCollector> Tokens;
+    };
+
+    class BuildSyntaxTreeAction : public ASTFrontendAction {
+    public:
+      BuildSyntaxTreeAction(syntax::TranslationUnit *&Root,
+                            std::unique_ptr<syntax::Arena> &Arena)
+          : Root(Root), Arena(Arena) {}
+
+      std::unique_ptr<ASTConsumer>
+      CreateASTConsumer(CompilerInstance &CI, StringRef InFile) override {
+        // We start recording the tokens, ast consumer will take on the result.
+        auto Tokens =
+            llvm::make_unique<syntax::TokenCollector>(CI.getPreprocessor());
+        return llvm::make_unique<BuildSyntaxTree>(Root, Arena,
+                                                  std::move(Tokens));
+      }
+
+    private:
+      syntax::TranslationUnit *&Root;
+      std::unique_ptr<syntax::Arena> &Arena;
+    };
+
+    constexpr const char *FileName = "./input.cpp";
+    FS->addFile(FileName, time_t(), llvm::MemoryBuffer::getMemBufferCopy(""));
+    // Prepare to run a compiler.
+    std::vector<const char *> Args = {"syntax-test", "-std=c++11",
+                                      "-fsyntax-only", FileName};
+    auto CI = createInvocationFromCommandLine(Args, Diags, FS);
+    assert(CI);
+    CI->getFrontendOpts().DisableFree = false;
+    CI->getPreprocessorOpts().addRemappedFile(
+        FileName, llvm::MemoryBuffer::getMemBufferCopy(Code).release());
+    CompilerInstance Compiler;
+    Compiler.setInvocation(std::move(CI));
+    if (!Diags->getClient())
+      Diags->setClient(new IgnoringDiagConsumer);
+    Compiler.setDiagnostics(Diags.get());
+    Compiler.setFileManager(FileMgr.get());
+    Compiler.setSourceManager(SourceMgr.get());
+
+    syntax::TranslationUnit *Root = nullptr;
+    BuildSyntaxTreeAction Recorder(Root, this->Arena);
+    if (!Compiler.ExecuteAction(Recorder)) {
+      ADD_FAILURE() << "failed to run the frontend";
+      std::abort();
+    }
+    return Root;
+  }
+
+  // Adds a file to the test VFS.
+  void addFile(llvm::StringRef Path, llvm::StringRef Contents) {
+    if (!FS->addFile(Path, time_t(),
+                     llvm::MemoryBuffer::getMemBufferCopy(Contents))) {
+      ADD_FAILURE() << "could not add a file to VFS: " << Path;
+    }
+  }
+
+  // Data fields.
+  llvm::IntrusiveRefCntPtr<DiagnosticsEngine> Diags =
+      new DiagnosticsEngine(new DiagnosticIDs, new DiagnosticOptions);
+  IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> FS =
+      new llvm::vfs::InMemoryFileSystem;
+  llvm::IntrusiveRefCntPtr<FileManager> FileMgr =
+      new FileManager(FileSystemOptions(), FS);
+  llvm::IntrusiveRefCntPtr<SourceManager> SourceMgr =
+      new SourceManager(*Diags, *FileMgr);
+  // Set after calling buildTree().
+  std::unique_ptr<syntax::Arena> Arena;
+};
+
+TEST_F(SyntaxTreeTest, Basic) {
+  std::pair</*Input*/ std::string, /*Expected*/ std::string> Cases[] = {
+      {
+          R"cpp(
+int main() {}
+void foo() {}
+    )cpp",
+          R"txt(
+*: TranslationUnit
+|-TopLevelDeclaration
+| |-int
+| |-main
+| |-(
+| |-)
+| `-CompoundStatement
+|   |-1: {
+|   `-2: }
+|-TopLevelDeclaration
+| |-void
+| |-foo
+| |-(
+| |-)
+| `-CompoundStatement
+|   |-1: {
+|   `-2: }
+`-<eof>
+)txt"},
+  };
+
+  for (const auto &T : Cases) {
+    auto *Root = buildTree(T.first);
+    std::string Expected = llvm::StringRef(T.second).trim().str();
+    std::string Actual = llvm::StringRef(Root->dump(*Arena)).trim();
+    EXPECT_EQ(Expected, Actual) << "the resulting dump is:\n" << Actual;
+  }
+}
+} // namespace