syntree

A memory efficient syntax tree.

This crate provides a tree structure which always is contiguously stored and manipulated in memory. It provides similar APIs as rowan and is intended to be an efficient replacement for it (read more below).

Usage

Add syntree to your crate:

syntree = "0.11.1"

If you want a complete sample for how syntree can be used for parsing, see the calculator example.

Enabling syntree_compact

We support a configuration option to reduce the size of the tree in memory. It changes the tree from using usize as indexes to use u32 which saves 4 bytes per reference on 64-bit platforms.

This can be enabled by setting --cfg syntree_compact while building and might improve performance due to allowing nodes to fit neatly on individual cache lines.

RUSTFLAGS="--cfg syntree_compact" cargo build

Syntax trees

This crate provides a way to efficiently model abstract syntax trees. The nodes of the tree are typically represented by variants in an enum, but could be whatever you want.

Each tree consists of nodes and tokens. Siblings are intermediary elements in the tree which encapsulate zero or more other nodes or tokens, while tokens are leaf elements representing exact source locations.

An example tree for the simple expression 256 / 2 + 64 * 2 could be represented like this:

[email protected]
  [email protected]
    [email protected] "256"
  [email protected] " "
  [email protected]
    [email protected] "/"
  [email protected] " "
  [email protected]
    [email protected] "2"
  [email protected] " "
  [email protected]
    [email protected] "+"
  [email protected] " "
  [email protected]
    [email protected]
      [email protected] "64"
    [email protected] " "
    [email protected]
      [email protected] "*"
    [email protected] " "
    [email protected]
      [email protected] "2"

Try it for yourself with:

cargo run --example calculator -- "256 / 2 + 64 * 2"

The primary difference between syntree and rowan is that we don't store the original source in the syntax tree. Instead, the user of the library is responsible for providing it as necessary. Like when calling print_with_source.

The API for constructing a syntax tree is provided through TreeBuilder which provides streaming builder methods. Internally the builder is represented as a contiguous slab of memory. Once a tree is built the structure of the tree can be queried through the Tree type.

Note that syntree::tree! is only a helper which simplifies building trees for examples. It corresponds exactly to performing open, close, and token calls on TreeBuilder as specified.

use syntree::{Span, TreeBuilder};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Syntax {
    NUMBER,
    LIT,
    NESTED,
}

use Syntax::*;

let mut tree = TreeBuilder::new();

tree.open(NUMBER)?;
tree.token(LIT, 1)?;
tree.token(LIT, 3)?;

tree.open(NESTED)?;
tree.token(LIT, 1)?;
tree.close()?;

tree.close()?;

let tree = tree.build()?;

let expected = syntree::tree! {
    NUMBER => {
        (LIT, 1),
        (LIT, 3),
        NESTED => {
            (LIT, 1)
        }
    }
};

assert_eq!(tree, expected);

let number = tree.first().ok_or("missing number")?;
assert_eq!(number.span(), Span::new(0, 5));

Note how the resulting Span for NUMBER corresponds to the full span of its LIT children. Including the ones within NESTED.

Trees are usually constructed by parsing an input. This library encourages the use of a handwritten pratt parser. See the calculator example for a complete use case.

Why not rowan?

I love rowan. It's the reason why I started this project. But this crate still exists for a few philosophical differences that would be hard to reconcile directly in rowan.

rowan only supports adding types which in some way can be coerced into an repr(u16) as part of the syntax tree. I think this decision is reasonable, but it precludes you from designing trees which contain anything else other than source references without having to perform some form of indirect lookup on the side. This is something I need in order to move Rune to lossless syntax trees (see the representation of Kind::Str variant).

To exemplify this scenario consider the following syntax:

#[derive(Debug, Clone, Copy)]
enum Syntax {
    /// A string referenced somewhere else using the provided ID.
    SYNTHETIC(Option<usize>),
    /// A literal string from the source.
    LITERAL,
    /// Whitespace.
    WHITESPACE,
    /// A lexer error.
    ERROR,
}

You can see the full synthetic_strings example for how this might be used. But not only can the SYNTHETIC token correspond to some source location (as it should because it was expanded from one!). It also directly represents that it's not a literal string referencing a source location.

In Rune this became apparent once we started expanding macros. Because macros expand to things which do not reference source locations so we need some other way to include what the tokens represent in the syntax trees.

You can try a very simple lex-time variable expander in the synthetic_strings example:

cargo run --example synthetic_strings -- "Hello $world"

Which would output:

Tree:
[email protected] "Hello"
[email protected] " "
SYNTHETIC(Some(0))@6..12 "$world"
Eval:
0 = "Hello"
1 = "Earth"

So in essense syntree doesn't believe you need to store strings in the tree itself. Even if you want to deduplicate string storage. All of that can be done on the side and encoded into the syntax tree as you wish.

Errors instead of panics

Another point where this crate differs is that we rely on propagating a TreeError during tree construction if the API is used incorrectly instead of panicking.

While on the surface this might seem like a minor difference in opinion on whether programming mistakes should be errors or not. In my experience parsers tend to be part of a crate in a larger project. And errors triggered by edge cases in user-provided input that once encountered can usually be avoided.

So let's say Rune is embedded in OxidizeBot and there's a piece of code in a user-provided script which triggers a bug in the rune compiler. Which in turn causes an illegal tree to be constructed. If tree construction simply panics, the whole bot will go down. But if we instead propagate an error this would have to be handled in OxidizeBot which could panic if it wanted to. In this instance it's simply more appropriate to log the error and unload the script (and hopefully receive a bug report!) than to crash the bot.

Rust has great diagnostics for indicating that results should be handled, and while it is more awkward to deal with results than to simply panic I believe that the end result is more robust software.

Performance and memory use

The only goal in terms of performance is to be as performant as rowan. And cursory testing shows syntree to be a bit faster on synthetic workloads which can probably be solely attributed to storing and manipulating the entire tree in a single contiguous memory region. This might or might not change in the future, depending on if the needs for syntree changes. While performance is important, it is not a primary focus.

I also expect (but haven't verified) that syntree could end up having a similarly low memory profile as rowan which performs node deduplication. The one caveat is that it depends on how the original source is stored and queried. Something which rowan solves for you, but syntree leaves as an exercise to the reader.

License: MIT/Apache-2.0