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).

Anything can be stored in the tree as long as it implements Copy.

Usage

Add syntree to your crate:

syntree = "0.18.0"

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

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][any-syntax].

Each tree consists of nodes and tokens. Nodes 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:

Operation@0..16
  Number@0..3
    Number@0..3 "256"
  Whitespace@3..4 " "
  Operator@4..5
    Div@4..5 "/"
  Whitespace@5..6 " "
  Number@6..7
    Number@6..7 "2"
  Whitespace@7..8 " "
  Operator@8..9
    Plus@8..9 "+"
  Whitespace@9..10 " "
  Operation@10..16
    Number@10..12
      Number@10..12 "64"
    Whitespace@12..13 " "
    Operator@13..14
      Mul@13..14 "*"
    Whitespace@14..15 " "
    Number@15..16
      Number@15..16 "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 [Builder] which implements 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 [Builder] as specified.

use syntree::{Builder, Span};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Syntax {
    Number,
    Lit,
    Nested,
}

use Syntax::*;

let mut tree = Builder::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][pratt]. See the [calculator example][calculator] for a complete use case.

Compact or empty spans

Spans by default uses u32-based indexes and usize-based pointers, this can be changed from its default using the [Builder::new_with] constructor:

use syntree::{Builder, Span, Tree};

syntree::flavor! {
    struct FlavorU16 {
        type Index = usize;
        type Width = u16;
    }
};

syntree::flavor! {
    struct FlavorU32 {
        type Index = usize;
        type Width = u32;
    }
};

let mut tree = Builder::<_, FlavorU16>::new_with();

tree.open("root")?;
tree.open("child")?;
tree.token("token", 100)?;
tree.close()?;
tree.open("child2")?;
tree.close()?;
tree.close()?;

let tree = tree.build()?;

let expected: Tree<_, FlavorU32> = syntree::tree_with! {
    "root" => {
        "child" => { ("token", 100) },
        "child2" => {}
    }
};

assert_eq!(tree, expected);
assert_eq!(tree.span(), Span::new(0, 100));

Combined with [Empty], this allows for building trees without spans, if that is something you want to do:

use syntree::{Builder, Empty, EmptyVec, TreeIndex, Tree};

syntree::flavor! {
    struct FlavorEmpty {
        type Index = Empty;
        type Indexes = EmptyVec<TreeIndex<Self>>;
    }
};

let mut tree = Builder::<_, FlavorEmpty>::new_with();

tree.open("root")?;
tree.open("child")?;
tree.token("token", Empty)?;
tree.close()?;
tree.open("child2")?;
tree.close()?;
tree.close()?;

let tree = tree.build()?;

let expected: Tree<_, FlavorEmpty> = syntree::tree_with! {
    "root" => {
        "child" => { "token" },
        "child2" => {}
    }
};

assert_eq!(tree, expected);
assert!(tree.span().is_empty());

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. This is something needed in order to move [Rune] to lossless syntax trees (see [the representation of Kind::Str variant][kind-str]).

To exemplify this scenario consider the following syntax:

#[derive(Debug, Clone, Copy)]
enum Syntax {
    /// A string referenced somewhere else using the provided ID.
    Synthetic(usize),
    /// A literal string from the source.
    Lit,
    /// Whitespace.
    Whitespace,
    /// A lexer error.
    Error,
}

You can see the [full synthetic_strings example][synthetic_strings] 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 needed once we started [expanding macros][rune-macros]. Because macros expand to things which do not reference source locations so we need some other mechanism 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][synthetic_strings]:

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

Which would output:

Tree:
Lit@0..5 "Hello"
Whitespace@5..6 " "
Synthetic(0)@6..12 "$world"
Eval:
0 = "Hello"
1 = "Earth"

So in essence 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 [Error] 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][syntree-math] than [to simply panic][rowan-math] 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.

Syntree

Install / Use

README

syntree

Usage

Syntax trees

Compact or empty spans

Why not `rowan`?

Errors instead of panics

Performance and memory use

Syntree

Install / Use

README

syntree

Usage

Syntax trees

Compact or empty spans

Why not rowan?

Errors instead of panics

Performance and memory use

Why not `rowan`?