cstree is a generic library for creating and working with concrete syntax trees.
“Traditional” abstract syntax trees (ASTs) usually contain different types of nodes which represent information
about the source text of a document and reduce this information to the minimal amount necessary to correctly
interpret it. In contrast, CSTs are lossless representations of the entire input where all tree nodes are
represented uniformly (i.e. the nodes are untyped), but include a
SyntaxKind field to determine the kind of
One of the big advantages of this representation is not only that it can recreate the original source exactly, but
also that it lends itself very well to the representation of incomplete or erroneous trees and is thus very suited
for usage in contexts such as IDEs.
The concept of and the data structures for CSTs are inspired in part by Swift’s libsyntax.
Trees consist of two layers: the inner tree (called green tree) contains the actual source text in position
independent green nodes. Tokens and nodes that appear identically at multiple places in the source text are
deduplicated in this representation in order to store the tree efficiently. This means that the green tree may not
structurally be a tree. To remedy this, the actual syntax tree is constructed on top of the green tree as a
secondary tree (called red tree), which models the exact source structure.
cstree implementation is a fork of the excellent
rowan, developed by the authors of rust-analyzer who wrote up a conceptual overview of their implementation in their repository.
Notable differences of
cstree compared to
- Syntax trees (red trees) are created lazily, but are persistent. Once a node has been created,
it will remain allocated, while
rowanre-creates the red layer on the fly. Apart from the trade-off discussed here, this helps to achieve good tree traversal speed while providing the next points:
- Syntax (red) nodes are
Sync, allowing to share realized trees across threads. This is achieved by atomically reference counting syntax trees as a whole, which also gets rid of the need to reference count individual nodes (helping with the point above).
- Syntax nodes can hold custom data.
cstreetrees are trees over interned strings. This means
cstreewill deduplicate the text of tokens such as identifiers with the same name. In this position,
rowanstores each string, with a small string optimization (see
- Performance optimizations for tree creation: only allocate new nodes on the heap if they are not in cache, avoid recursively hashing subtrees
- Performance optimizations for tree traversal: persisting red nodes allows tree traversal methods to return
references. You can still
cloneto obtain an owned node, but you only pay that cost when you need to.
cstree is built for concrete syntax trees, applications are quite easily able to work with either a CST or
an AST representation, or freely switch between them. To do so, use
cstree to build syntax and underlying green
tree and provide AST wrappers for your different kinds of nodes. An example of how this is done can be seen here and here (note that the latter file is automatically generated by a task).
Types and Traits for efficient String storage and deduplication.
Implementation of the outer, “red” tree.
An atomically reference counted shared pointer
A checkpoint for maybe wrapping a node. See
An iterator over a
Internal node in the immutable “green” tree. It contains other nodes and tokens as its children.
A builder for green trees.
Leaf node in the immutable “green” tree.
SyntaxKind is a type tag for each token or node.
A range in text, represented as a pair of
A measure of text length. Also, equivalently, an index into text.
Convenience type to represent tree elements which may either be a node or a token.
There might be zero, one or two leaves at a given offset.
Primitives with a textual length that can be passed to