A memory efficient syntax tree for language developers

Overview

syntree

github crates.io docs.rs build status

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:

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

You might also like...
Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

A sparse merkle tree lib focused on efficient on-chain proofs. Enforces ordering within the merkle tree.

sparse-merkle-tree The merkle tree functions are located in sparse.ak. Currently the supported functionality is: Verifying a new root with an added me

a simple compiled language i made in rust. it uses intermediate representation (IR) instead of an abstract syntax tree (AST).

a simple compiled language i made in rust. it uses intermediate representation (IR) instead of an abstract syntax tree (AST).

Nexa programming language. A language for game developers by a game developer
Nexa programming language. A language for game developers by a game developer

NexaLang Nexa programming language. A language for game developers by a game developer. Features High-Level: Nexa is an easy high level language Two M

syntect is a syntax highlighting library for Rust that uses Sublime Text syntax definitions.
syntect is a syntax highlighting library for Rust that uses Sublime Text syntax definitions.

syntect is a syntax highlighting library for Rust that uses Sublime Text syntax definitions. It aims to be a good solution for any Rust project that needs syntax highlighting, including deep integration with text editors written in Rust.

A syntax highlighter for Node powered by Tree Sitter. Written in Rust.

tree-sitter-highlight A syntax highlighter for Node.js powered by Tree Sitter. Written in Rust. Usage The following will output HTML: const treeSitter

A minimal `syn` syntax tree pretty-printer

prettyplease::unparse A minimal syn syntax tree pretty-printer. Overview This is a pretty-printer to turn a syn syntax tree into a String of well-form

A Markdown to HTML compiler and Syntax Highlighter, built using Rust's pulldown-cmark and tree-sitter-highlight crates.

A blazingly fast( possibly the fastest) markdown to html parser and syntax highlighter built using Rust's pulldown-cmark and tree-sitter-highlight crate natively for Node's Foreign Function Interface.

Build Abstract Syntax Trees and tree-walking models quickly in Rust.

astmaker Build Abstract Syntax Trees and tree-walking models quickly in Rust. Example This example creates an AST for simple math expressions, and an

A pure-rust(with zero dependencies) fenwick tree, for the efficient computation of dynamic prefix sums.

indexset A pure-rust(with zero dependencies, no-std) fenwick tree, for the efficient computation of dynamic prefix sums. Background Did you ever have

Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface

tree-sitter-traversal Traversal of tree-sitter Trees and any arbitrary tree with a TreeCursor-like interface. Using cursors, iteration over the tree c

As-tree - Print a list of paths as a tree of paths 🌳

as-tree Print a list of paths as a tree of paths. For example, given: dir1/foo.txt dir1/bar.txt dir2/qux.txt it will print: . ├── dir1 │ ├── foo.tx

Nearest neighbor search algorithms including a ball tree and a vantage point tree.

petal-neighbors Nearest neighbor search algorithms including a ball tree and a vantage point tree. Examples The following example shows how to find tw

Untree converts tree diagrams produced by tree back into directory file structures.
Untree converts tree diagrams produced by tree back into directory file structures.

Untree: Undoing tree for fun and profit Untree converts tree diagrams produced by tree back into directory file structures. Let's say you have the fol

A comprehensive collection of resources and learning materials for Rust programming, empowering developers to explore and master the modern, safe, and blazingly fast language.

🦀 Awesome Rust Lang ⛰️ Project Description : Welcome to the Awesome Rust Lang repository! This is a comprehensive collection of resources for Rust, a

A programming language for developers 💻

DevScript DevScript DevScript is a programming language for developers 💻 Authors: Note: this section will be changed to be more sophisticated, as to

tr-lang is a language that aims to bring programming language syntax closer to Turkish.

tr-lang Made with ❤️ in 🇹🇷 tr-lang is a language that aims to bring programming language syntax closer to Turkish. tr-lang is a stack based language

Proof-of-concept for a memory-efficient data structure for zooming billion-event traces

Proof-of-concept for a gigabyte-scale trace viewer This repo includes: A memory-efficient representation for event traces An unusually simple and memo

A memory efficient immutable string type that can store up to 24* bytes on the stack

compact_str A memory efficient immutable string type that can store up to 24* bytes on the stack. * 12 bytes for 32-bit architectures About A CompactS

Comments
  • Implement find_preceding

    Implement find_preceding

    This can be used to find a point span which ends at a given node after a call to node_with_range. Which might be useful to determine something like the node that is just preceding the point being edited.

    enhancement 
    opened by udoprog 0
  • Start work on checkpoint

    Start work on checkpoint

    This introduces basic checkpoints which ensures a well-balanced tree.

    Checkpointing is used to decide late in a parsing process what node to emit.

    use anyhow::Result;
    use syntree::{print, Span, TreeBuilder};
    
    #[derive(Debug, Clone, Copy)]
    enum Syntax {
        Root,
        Number,
        Lit,
        Whitespace,
    }
    
    fn main() -> Result<()> {
        let mut b = TreeBuilder::new();
    
        let c = b.checkpoint();
    
        b.start_node(Syntax::Number);
        b.token(Syntax::Lit, Span::new(1, 2));
        b.end_node()?;
    
        b.token(Syntax::Whitespace, Span::new(2, 5));
    
        b.start_node(Syntax::Number);
        b.token(Syntax::Lit, Span::new(5, 7));
        b.token(Syntax::Lit, Span::new(7, 9));
        b.end_node()?;
    
        b.insert_node_at(c, Syntax::Root);
    
        let tree = b.build()?;
    
        print::print(&mut std::io::stdout(), &tree)?;
        Ok(())
    }
    
    opened by udoprog 0
Owner
John-John Tedro
Same username on Telegram, Twitter. setbac on Discord and Twitch. Hit me up if you want to talk!
John-John Tedro
A comprehensive memory scanning library

scanflow boasts a feature set similar to the likes of CheatEngine, with a simple command line interface. Utilizing memflow, scanflow works in a wide range of situations - from virtual machines, to dedicated DMA hardware.

memflow 38 Dec 30, 2022
MiniDump a process in memory with rust

safetydump Rust in-memory MiniDump implementation. Features ntdll!NtGetNextProcess to obtain a handle for the desired ProcessId as opposed to kernel32

null 26 Oct 11, 2022
In-memory, non stateful and session based code sharing application.

interviewer In-memory, non stateful and session based code sharing application. Test it here: interviewer.taras.lol Note: it's deployed to render auto

2pac 7 Aug 16, 2021
A cross-platform and safe Rust API to create and manage memory mappings in the virtual address space of the calling process.

mmap-rs A cross-platform and safe Rust API to create and manage memory mappings in the virtual address space of the calling process. This crate can be

S.J.R. van Schaik 19 Oct 23, 2022
Cross-platform library for reading/writing memory in other processes for Rust

vmemory Rust library for reading/writing memory in other processes for Windows, macOS, Linux, and in the future potentially, BSD variants. Rationale A

Jason Johnson 26 Nov 7, 2022
Rust library to interract with memory written in rust

memory-rs Rust library to interract with memory written in rust It comes with: Pattern scanner (Return address for a pattern given). A pattern example

Alex 1 Jan 13, 2022
bevy_datasize is a library for tracking memory usage in Bevy apps.

bevy_datasize bevy_datasize is a library for tracking memory usage in Bevy apps. bevy_datasize uses the DataSize trait from the datasize crate to esti

Ben Reeves 4 Mar 8, 2022
Compile-time checked Builder pattern derive macro with zero-memory overhead

Compile-time checked Builder pattern derive macro with zero-memory overhead This is very much a work-in-progress. PRs welcome to bring this to product

Esteban Kuber 214 Dec 29, 2022
Memory hacking library for windows

Memory hacking library for windows

Sara Wahib 4 Apr 11, 2022
Count your code by tokens, types of syntax tree nodes, and patterns in the syntax tree. A tokei/scc/cloc alternative.

tcount (pronounced "tee-count") Count your code by tokens, types of syntax tree nodes, and patterns in the syntax tree. Quick Start Simply run tcount

Adam P. Regasz-Rethy 48 Dec 7, 2022