cstree

<strong>A library for generic lossless syntax trees</strong>







<a href="https://github.com/domenicquirl/cstree/actions?query=workflow%3ACI"> <img src="https://img.shields.io/github/actions/workflow/status/domenicquirl/cstree/main.yml?branch=master&logo=github&style=for-the-badge" alt="build status" /></a>
<a href="https://docs.rs/cstree/"> <img src="https://img.shields.io/badge/docs.rs-cstree-66c2a5?style=for-the-badge&labelColor=555555&logoColor=white&logo=data:image/svg+xml;base64,PHN2ZyByb2xlPSJpbWciIHhtbG5zPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZyIgdmlld0JveD0iMCAwIDUxMiA1MTIiPjxwYXRoIGZpbGw9IiNmNWY1ZjUiIGQ9Ik00ODguNiAyNTAuMkwzOTIgMjE0VjEwNS41YzAtMTUtOS4zLTI4LjQtMjMuNC0zMy43bC0xMDAtMzcuNWMtOC4xLTMuMS0xNy4xLTMuMS0yNS4zIDBsLTEwMCAzNy41Yy0xNC4xIDUuMy0yMy40IDE4LjctMjMuNCAzMy43VjIxNGwtOTYuNiAzNi4yQzkuMyAyNTUuNSAwIDI2OC45IDAgMjgzLjlWMzk0YzAgMTMuNiA3LjcgMjYuMSAxOS45IDMyLjJsMTAwIDUwYzEwLjEgNS4xIDIyLjEgNS4xIDMyLjIgMGwxMDMuOS01MiAxMDMuOSA1MmMxMC4xIDUuMSAyMi4xIDUuMSAzMi4yIDBsMTAwLTUwYzEyLjItNi4xIDE5LjktMTguNiAxOS45LTMyLjJWMjgzLjljMC0xNS05LjMtMjguNC0yMy40LTMzLjd6TTM1OCAyMTQuOGwtODUgMzEuOXYtNjguMmw4NS0zN3Y3My4zek0xNTQgMTA0LjFsMTAyLTM4LjIgMTAyIDM4LjJ2LjZsLTEwMiA0MS40LTEwMi00MS40di0uNnptODQgMjkxLjFsLTg1IDQyLjV2LTc5LjFsODUtMzguOHY3NS40em0wLTExMmwtMTAyIDQxLjQtMTAyLTQxLjR2LS42bDEwMi0zOC4yIDEwMiAzOC4ydi42em0yNDAgMTEybC04NSA0Mi41di03OS4xbDg1LTM4Ljh2NzUuNHptMC0xMTJsLTEwMiA0MS40LTEwMi00MS40di0uNmwxMDItMzguMiAxMDIgMzguMnYuNnoiPjwvcGF0aD48L3N2Zz4K" alt="documentation" /></a>
<a href="https://crates.io/crates/cstree"> <img src="https://img.shields.io/crates/v/cstree?logo=rust&style=for-the-badge" alt="crates.io" /></a>
<img src="https://img.shields.io/crates/l/cstree?style=for-the-badge&logoColor=white&logo=data:image/svg+xml;base64,PHN2ZyB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIGFyaWEtaGlkZGVuPSJ0cnVlIiBoZWlnaHQ9IjE2IiB2aWV3Qm94PSIwIDAgMTYgMTYiIHZlcnNpb249IjEuMSIgd2lkdGg9IjE2IiBkYXRhLXZpZXctY29tcG9uZW50PSJ0cnVlIiBjbGFzcz0ib2N0aWNvbiBvY3RpY29uLWxhdyBtci0yIj4KICAgIDxwYXRoIGZpbGw9IndoaXRlIiBkPSJNOC43NS43NVYyaC45ODVjLjMwNCAwIC42MDMuMDguODY3LjIzMWwxLjI5LjczNmMuMDM4LjAyMi4wOC4wMzMuMTI0LjAzM2gyLjIzNGEuNzUuNzUgMCAwIDEgMCAxLjVoLS40MjdsMi4xMTEgNC42OTJhLjc1Ljc1IDAgMCAxLS4xNTQuODM4bC0uNTMtLjUzLjUyOS41MzEtLjAwMS4wMDItLjAwMi4wMDItLjAwNi4wMDYtLjAwNi4wMDUtLjAxLjAxLS4wNDUuMDRjLS4yMS4xNzYtLjQ0MS4zMjctLjY4Ni40NUMxNC41NTYgMTAuNzggMTMuODggMTEgMTMgMTFhNC40OTggNC40OTggMCAwIDEtMi4wMjMtLjQ1NCAzLjU0NCAzLjU0NCAwIDAgMS0uNjg2LS40NWwtLjA0NS0uMDQtLjAxNi0uMDE1LS4wMDYtLjAwNi0uMDA0LS4wMDR2LS4wMDFhLjc1Ljc1IDAgMCAxLS4xNTQtLjgzOEwxMi4xNzggNC41aC0uMTYyYy0uMzA1IDAtLjYwNC0uMDc5LS44NjgtLjIzMWwtMS4yOS0uNzM2YS4yNDUuMjQ1IDAgMCAwLS4xMjQtLjAzM0g4Ljc1VjEzaDIuNWEuNzUuNzUgMCAwIDEgMCAxLjVoLTYuNWEuNzUuNzUgMCAwIDEgMC0xLjVoMi41VjMuNWgtLjk4NGEuMjQ1LjI0NSAwIDAgMC0uMTI0LjAzM2wtMS4yODkuNzM3Yy0uMjY1LjE1LS41NjQuMjMtLjg2OS4yM2gtLjE2MmwyLjExMiA0LjY5MmEuNzUuNzUgMCAwIDEtLjE1NC44MzhsLS41My0uNTMuNTI5LjUzMS0uMDAxLjAwMi0uMDAyLjAwMi0uMDA2LjAwNi0uMDE2LjAxNS0uMDQ1LjA0Yy0uMjEuMTc2LS40NDEuMzI3LS42ODYuNDVDNC41NTYgMTAuNzggMy44OCAxMSAzIDExYTQuNDk4IDQuNDk4IDAgMCAxLTIuMDIzLS40NTQgMy41NDQgMy41NDQgMCAwIDEtLjY4Ni0uNDVsLS4wNDUtLjA0LS4wMTYtLjAxNS0uMDA2LS4wMDYtLjAwNC0uMDA0di0uMDAxYS43NS43NSAwIDAgMS0uMTU0LS44MzhMMi4xNzggNC41SDEuNzVhLjc1Ljc1IDAgMCAxIDAtMS41aDIuMjM0YS4yNDkuMjQ5IDAgMCAwIC4xMjUtLjAzM2wxLjI4OC0uNzM3Yy4yNjUtLjE1LjU2NC0uMjMuODY5LS4yM2guOTg0Vi43NWEuNzUuNzUgMCAwIDEgMS41IDBabTIuOTQ1IDguNDc3Yy4yODUuMTM1LjcxOC4yNzMgMS4zMDUuMjczczEuMDItLjEzOCAxLjMwNS0uMjczTDEzIDYuMzI3Wm0tMTAgMGMuMjg1LjEzNS43MTguMjczIDEuMzA1LjI3M3MxLjAyLS4xMzggMS4zMDUtLjI3M0wzIDYuMzI3WiIvPgo8L3N2Zz4=" alt="licenses" />

cstree is a generic library for creating and working with concrete syntax trees (CSTs). "Traditional" abstract syntax trees (ASTs) usually contain different types of nodes which represent different syntactical elements of the source text of a document and reduce its 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 homogeneously (i.e., the nodes are untyped), but are tagged with a RawSyntaxKind to determine the kind of grammatical element they represent. One big advantage of this representation is that it cannot only recreate the original source exactly, but also lends itself very well to the representation of incomplete or erroneous trees and is thus highly suited for usage in contexts such as IDEs or any other application where a user is editing the source text. The concept of and the data structures for cstree's syntax trees are inspired in part by Swift's libsyntax. Trees consist of two layers: the inner tree (called green tree) contains the actual source text as position independent green nodes. Tokens and nodes that appear identically at multiple places in the source are deduplicated in this representation in order to store the tree efficiently. This means that a green tree may not actually structurally be a tree. To remedy this, the real syntax tree is constructed on top of the green tree as a secondary tree (called the red tree), which models the exact source structure. As a possible third layer, a strongly typed AST can be built on top of the red tree.

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 red node has been created by cstree, it will remain allocated. In contrast, rowan re-creates the red layer on the fly on each traversal of the tree. Apart from the trade-off discussed here, this helps to achieve good tree traversal speed while helping to provide the following: - Syntax (red) nodes are Send and 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. - SyntaxNodes can hold custom data. - cstree trees are trees over interned strings. This means cstree will deduplicate the text of tokens with the same source string, such as identifiers with the same name. In this position, rowan stores each token's text together with its metadata as a custom DST (dynamically-sized type). - cstree includes some performance optimizations for tree creation: it only allocates space for new nodes on the heap if they are not in cache and avoids recursively hashing subtrees by pre-hashing them. - cstree includes some performance optimizations for tree traversal: persisting red nodes allows tree traversal methods to return references instead of cloning nodes, which involves updating the tree's reference count. You can still clone the reference to obtain an owned node, but you only pay that cost when you need to. - The downside of offering thread safe syntax trees is that cstree cannot offer any mutability API for its CSTs. Trees can still be updated into new trees through replacing nodes, but cannot be mutated in place. - cstree is also fully compatible with #[no_std] by disabling the std feature and including a global allocator with the alloc crate. However, disabling the std feature disables some optimizations that are not possible in no_std contexts.

Cargo Feature Flags

cstree contains several optional features that extend the crate’s functionality.

• std (enabled by default) - Support for standard library features
• derive - Adds support for deriving the Syntax trait
• serialize - Implements serde::{De,}Serialize for CSTs
• lasso - Allows using interners from the lasso crate for green trees.
• When enabled, cstree's default interners will use lasso internally, too.
• multi_threaded_interning - Additionally provide threadsafe interner types.
• Where applicable (and if the corresponding features are selected), enabling this feature will also make cstree provide compatibility implementations for multi-threaded interners from other crates.
• Enabling this feature will automatically enable the lasso feature, as the multi-threaded interners are backed by lasso.

Getting Started

If you're looking at cstree, you're probably looking at or already writing a parser and are considering using concrete syntax trees as its output. We'll talk more about parsing below -- first, let's have a look at what needs to happen to go from input text to a cstree syntax tree:

1. Define an enumeration of the types of tokens (like keywords) and nodes (like "an expression") that you want to have in your syntax and implement Syntax

2. Create a GreenNodeBuilder and call start_node, token and finish_node from your parser

3. Call SyntaxNode::new_root or SyntaxNode::new_root_with_resolver with the resulting GreenNode to obtain a syntax tree that you can traverse

Let's walk through the motions of parsing a (very) simple language into cstree syntax trees. We'll just support addition and subtraction on integers, from which the user is allowed to construct a single, compound expression. They will, however, be allowed to write nested expressions in parentheses, like 1 - (2 + 5).

Defining the language

First, we need to list the different part of our language's grammar. We can do that using an enum with a unit variant for any terminal and non-terminal. The enum needs to be convertible to a u32, so we use the repr attribute to ensure it uses the correct representation.

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(u32)]
enum SyntaxKind {
    /* Tokens */
    Int,    // 42
    Plus,   // +
    Minus,  // -
    LParen, // (
    RParen, // )
    /* Nodes */
    Expr,
    Root,
}

For convenience when we're working with generic cstree types like SyntaxNode, we'll also give a name to our syntax as a whole and add a type alias for it. That way, we can match against SyntaxKinds using the original name, but use the more informative Node<Calculator> to instantiate cstree's types.

type Calculator = SyntaxKind;

Most of these are tokens to lex the input string into, like numbers (Int) and operators (Plus, Minus). We only really need one type of node; expressions. Our syntax tree's root node will have the special kind Root, all other nodes will be expressions containing a sequence of arithmetic operations potentially involving further, nested expression nodes.

To use our SyntaxKinds with cstree, we need to tell it how to convert it back to just a number (the #[repr(u32)] that we added) by implementing the Syntax trait. We can also tell cstree about tokens that always have the same text through the static_text method on the trait. This is useful for the operators and parentheses, but not possible for numbers, since an integer token may be produced from the input 3, but also from other numbers like 7 or 12. We implement Syntax on an empty type, just so we can give it a name.

impl Syntax for Calculator { 
    fn from_raw(raw: RawSyntaxKind) -> Self {
        // This just needs to be the inverse of `into_raw`, but could also
        // be an `impl TryFrom<u32> for SyntaxKind` or any other conversion.
        match raw.0 {
            0 => SyntaxKind::Int,
            1 => SyntaxKind::Plus,
            2 => SyntaxKind::Minus,
            3 => SyntaxKind::LParen,
            4 => SyntaxKind::RParen,
            5 => SyntaxKind::Expr,
            6 => SyntaxKind::Root,
            n => panic!("Unknown raw syntax kind: {n}"),
        }
    }

    fn into_raw(self) -> RawSyntaxKind {
        RawSyntaxKind(self as u32)
    }

    fn static_text(self) -> Option<&'static str> {
        match self {
            SyntaxKind::Plus => Some("+"),
            SyntaxKind::Minus => Some("-"),
            SyntaxKind::LParen => Some("("),
            SyntaxKind::RParen => Some(")"),
            _ => None,
        }
    }
}

Deriving Syntax

To save yourself the hassle of defining this conversion (and, perhaps more importantly, continually updating it while your language's syntax is in flux), cstree includes a derive macro for Syntax when built with the derive feature. With the macro, the Syntax trait implementation above can be replaced by simply adding #[derive(Syntax)] to SyntaxKind.

Parsing into a green tree

With that out of the way, we can start writing the parser for our expressions. For the purposes of this introduction to cstree, I'll assume that there is a lexer that yields the following tokens:

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum Token<'input> {
    // Note that number strings are not yet parsed into actual numbers,
    // we just remember the slice of the input that contains their digits
    Int(&'input str),
    Plus,
    Minus,
    LParen,
    RParen,
    // A special token that indicates that we have reached the end of the file
    EoF,
}

A simple lexer that yields such tokens is part of the full readme example, but we'll be busy enough with the combination of cstree and the actual parser, which we define like this:

``rust pub struct Parser<'input> { //Peekable` is a standard library iterator adapter that allows // looking ahead at the next item without removing it from the iterator yet lexer: Peekable<Lexer<'input>>, builder: GreenNodeBuilder<'static,