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

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
  NUMBER@0..3 "128"
<< NUMBER
WHITESPACE@3..4 " "
>> OPERATOR
  PLUS@4..5 "+"
<< OPERATOR
WHITESPACE@5..6 " "
>> NUMBER
  NUMBER@6..8 "64"
<< NUMBER

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.

use syntree::{Span, TreeBuilder};

#[derive(Debug, Clone, Copy)]
enum Syntax {
    OPERATION,
    NUMBER,
    PLUS,
    MINUS,
    WHITESPACE,
}

use Syntax::*;

let mut b = TreeBuilder::new();

b.start_node(OPERATION);

b.start_node(OPERATION);

b.start_node(NUMBER);
b.token(NUMBER, 4);
b.end_node()?;

b.token(WHITESPACE, 1);

b.start_node(PLUS);
b.token(PLUS, 1);
b.end_node()?;

b.token(WHITESPACE, 1);

b.start_node(NUMBER);
b.token(NUMBER, 5);
b.end_node()?;

b.end_node()?;

b.token(WHITESPACE, 1);

b.start_node(MINUS);
b.token(MINUS, 1);
b.end_node()?;

b.token(WHITESPACE, 1);

b.start_node(NUMBER);
b.token(NUMBER, 3);
b.end_node()?;

b.end_node()?;

let tree = b.build()?;

assert_eq!(tree.span().range(), 0..18);
assert_eq!(tree.children().count(), 1);

License: MIT/Apache-2.0