cstree is a library for creating and working with concrete syntax trees (CSTs).
"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 node.
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.
The 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 rowan:
- 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
SendandSync, 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 meanscstreewill deduplicate the text of tokens such as identifiers with the same name. In this position,rowanstores each string, with a small string optimization (seeSmolStr).- 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.
Getting Started
The main entry points for constructing syntax trees are GreenNodeBuilder and SyntaxNode::new_root for green and red trees respectively.
See examples/s_expressions for a guided tutorial to cstree.
AST Layer
While 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).
License
cstree is primarily distributed under the terms of both the MIT license and the Apache License (Version 2.0).
See LICENSE-APACHE and LICENSE-MIT for details.