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.9.1"

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

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. 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 128 + 64 could be represented like this:

Try it for yourself with:

cargo run --example calculator -- "128 + 64"

NUMBER@0..3
  NUMBER@0..3 "128"
WHITESPACE@3..4 " "
OPERATOR@4..5
  PLUS@4..5 "+"
WHITESPACE@5..6 " "
NUMBER@6..8
  NUMBER@6..8 "64"

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 below, syntree::tree! is only a helper which simplifies building trees for examples. It corresponds exactly to performing the corresponding open and close calls on TreeBuilder.

use syntree::{Span, TreeBuilder};

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

use Syntax::*;

let mut b = TreeBuilder::new();

b.open(NUMBER);
b.token(LIT, 1);
b.token(LIT, 3);

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

b.close()?;

let tree = b.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.

License: MIT/Apache-2.0