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

Overview

tree-sitter-traversal

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

build_status Documentation crates.io

Using cursors, iteration over the tree can be implemented in a very efficient manner which performs no additional heap allocation beyond what might be required by the Cursor. The state required for pre-order and post-order traversal is very minimal; for pre-order traversal, all that is required is to maintain whether the traversal is complete, and for post-order traversal, we also maintain if the cursor is currently traversing up or down the tree.

Usage

Add this to your Cargo.toml

[dependencies]
tree-sitter-traversal = "0.1.2"

Example

usize { x * 2 }", None).expect("Error parsing provided code"); } fn main() { use std::collections::HashSet; use std::iter::FromIterator; let tree: Tree = get_tree(); let preorder: Vec <'_>> = traverse(tree.walk(), Order::Pre).collect:: <_>>(); let postorder: Vec <'_>> = traverse_tree(&tree, Order::Post).collect:: <_>>(); // For any tree with more than just a root node, // the order of preorder and postorder will be different assert_ne!(preorder, postorder); // However, they will have the same amount of nodes assert_eq!(preorder.len(), postorder.len()); // Specifically, they will have the exact same nodes, just in a different order assert_eq!( <_>>::from_iter(preorder.into_iter()), <_>>::from_iter(postorder.into_iter()) ); }">
use tree_sitter::{Node, Tree};

use tree_sitter_traversal::{traverse, traverse_tree, Order};
fn get_tree() -> Tree {
    use tree_sitter::Parser;
    let mut parser = Parser::new();
    let lang = tree_sitter_rust::language();
    parser.set_language(lang).expect("Error loading Rust grammar");
    return parser.parse("fn double(x: usize) -> usize { x * 2 }", None).expect("Error parsing provided code");
}

fn main() {
    use std::collections::HashSet;
    use std::iter::FromIterator;
    let tree: Tree = get_tree();
    let preorder: Vec<Node<'_>> = traverse(tree.walk(), Order::Pre).collect::<Vec<_>>();
    let postorder: Vec<Node<'_>> = traverse_tree(&tree, Order::Post).collect::<Vec<_>>();
    // For any tree with more than just a root node,
    // the order of preorder and postorder will be different
    assert_ne!(preorder, postorder);
    // However, they will have the same amount of nodes
    assert_eq!(preorder.len(), postorder.len());
    // Specifically, they will have the exact same nodes, just in a different order
    assert_eq!(
        <HashSet<_>>::from_iter(preorder.into_iter()),
        <HashSet<_>>::from_iter(postorder.into_iter())
    );   
}

Features

Though this library was designed to be used for tree-sitter, that usage is optional, as it can also be used by any struct which implements the Cursor trait. When the tree-sitter feature is disabled, the library is actually #![no_std]. To use without tree-sitter, add this to your Cargo.toml instead:

[dependencies.tree-sitter-traversal]
version = "0.1.2"
default-features = false
You might also like...
Standard Graphics is a command-line tool for printing 2D graphics from any language to any screen.
Standard Graphics is a command-line tool for printing 2D graphics from any language to any screen.

2D graphics in any programming language with just print statements!

A fun rust terminal program so you can make Christmas trees!
A fun rust terminal program so you can make Christmas trees!

Xmastree 2021 A fun christmas tree where you can add ornaments! Then, you can export the file into either: a rust file a txt file About Taking a break

Memory usage monitor for process trees

gotta-watch-em-all Executes a process with given arguments and monitors, logs when memory usage grows to a new peak. Example: cargo run -- cargo -- bu

Blazingly fast interpolated LUT generator and applicator for arbitrary and popular color palettes.
Blazingly fast interpolated LUT generator and applicator for arbitrary and popular color palettes.

lutgen-rs A blazingly fast interpolated LUT generator and applicator for arbitrary and popular color palettes. Theme any image to your dekstop colorsc

A library that allows for the arbitrary inspection and manipulation of the memory and code of a process on a Linux system.
A library that allows for the arbitrary inspection and manipulation of the memory and code of a process on a Linux system.

raminspect raminspect is a crate that allows for the inspection and manipulation of the memory and code of a running process on a Linux system. It pro

AI-TOML Workflow Specification (aiTWS), a comprehensive and flexible specification for defining arbitrary Ai centric workflows.

AI-TOML Workflow Specification (aiTWS) The AI-TOML Workflow Specification (aiTWS) is a flexible and extensible specification for defining arbitrary wo

Encode and decode dynamically constructed values of arbitrary shapes to/from SCALE bytes

scale-value · This crate provides a Value type, which is a runtime representation that is compatible with scale_info::TypeDef. It somewhat analogous t

a universal meta-transliterator that can decipher arbitrary encoding schemas, built in pure Rust
a universal meta-transliterator that can decipher arbitrary encoding schemas, built in pure Rust

transliterati a universal meta-transliterator that can decipher arbitrary encoding schemas, built in pure Rust what does it do? You give it this: Барл

A PoC for the CVE-2022-44268 - ImageMagick arbitrary file read
A PoC for the CVE-2022-44268 - ImageMagick arbitrary file read

CVE-2022-44268 Arbitrary File Read PoC - PNG generator This is a proof of concept of the ImageMagick bug discovered by https://www.metabaseq.com/image

Owner
Sebastian Mendez
Software Engineering Intern at Airbnb. Former member of the Viral Communications Team in the MIT MediaLab, working on the SuperGlue project.
Sebastian Mendez
Semantic find-and-replace using tree-sitter-based macro expansion

Semantic find-and-replace using tree-sitter-based macro expansion

Isaac Clayton 15 Nov 10, 2022
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

Devon Govett 211 Dec 20, 2022
Tree-sitter - An incremental parsing system for programming tools

tree-sitter Tree-sitter is a parser generator tool and an incremental parsing library. It can build a concrete syntax tree for a source file and effic

null 10.6k Jan 9, 2023
A tree-sitter based AST difftool to get meaningful semantic diffs

diffsitter Disclaimer diffsitter is very much a work in progress and nowhere close to production ready (yet). Contributions are always welcome! Summar

Afnan Enayet 1.3k Jan 8, 2023
Mypyc DSL grammar for tree-sitter

tree-sitter-mypyc Mypyc DSL grammar for tree-sitter. Installing (Neovim) This is based on the Neovim Tree-sitter docs for adding new parsers. Basicall

dosisod 3 Dec 30, 2022
tree-sitter meets Kakoune

kak-tree-sitter This is a binary server that interfaces tree-sitter with kakoune. Features Install Usage Design Credits Features Semantic highlighting

Dimitri Sabadie 5 May 3, 2023
rehype plugin to use tree-sitter to highlight code in pre code blocks

rehype-tree-sitter rehype plugin to use tree-sitter to highlight code in <pre><code> blocks Contents What is this? When should I use this? Install Use

null 5 Jul 25, 2023
Abuse the node.js inspector mechanism in order to force any node.js/electron/v8 based process to execute arbitrary javascript code.

jscythe abuses the node.js inspector mechanism in order to force any node.js/electron/v8 based process to execute arbitrary javascript code, even if t

Simone Margaritelli 301 Jan 4, 2023
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

David Delassus 100 Jun 5, 2023
To help prevent directory traversal attacks

safe_join Use SafeJoin::safe_join in place of Path::join to help prevent directory traversal attacks. A call of the form dir.safe_join(path) returns a

Trail of Bits 1 Dec 27, 2021