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.
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.
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:
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. See the calculator example for a complete use case.
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};
let mut tree = Builder::<_, usize, u16>::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<_, usize, u32> = 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, Tree};
let mut tree = Builder::<_, Empty, u32>::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<_, Empty, usize> = syntree::tree_with! {
"root" => {
"child" => { "token" },
"child2" => {}
}
};
assert_eq!(tree, expected);
assert!(tree.span().is_empty());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).
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 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. 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:
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.
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 than to simply panic I believe that the end result is more robust software.
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.