Crate linked_syntax_tree
source ·Expand description
A doubly-linked syntax tree.
Offers functionality similar to std::collections::LinkedList
.
Example
x = -10
loop
x = x + 1
if x
break
x = 2
can be represented as:
┌──────────┐
│x = -10 │
└──────────┘
│
┌──────────┐
│loop │
└──────────┘
│ ╲
┌──────────┐ ┌─────────┐
│x = 2 │ │x = x + 1│
└──────────┘ └─────────┘
│
┌─────────┐
│if x │
└─────────┘
╲
┌─────────┐
│break │
└─────────┘
which can be constructed with:
let mut root = SyntaxTree::default();
let mut cursor = root.cursor_mut();
cursor.insert_next("x = -10"); // Inserts "x = -10" as the root element.
cursor.insert_next("loop"); // Inserts "loop" as the next element.
cursor.move_next(); // Moves the cursor to "loop".
cursor.insert_child("x = x + 1"); // Inserts "x = x + 1" as the child element.
cursor.move_child(); // Moves the cursor to "x = x + 1".
cursor.insert_next("if x"); // Inserts "if x" as the next element.
cursor.move_next(); // Moves the cursor to "if x".
cursor.insert_child("break"); // Inserts "break" as the child element.
cursor.move_parent(); // Moves the cursor to "if x".
cursor.move_parent(); // Moves the cursor to "loop".
cursor.insert_next("x = 2");
assert_eq!(root.to_string(), r#"x = -10
loop
x = x + 1
if x
break
x = 2
"#);
Terminology
- next:
loop
is the next element ofx = -10
. - previous:
x = -10
is the previous element ofloop
. - child:
x = x + 1
is the child element ofloop
. - parent:
loop
is the parent element ofx = x + 1
. - preceding: All previous elements and parent elements are preceding elements. A preceding element may be a previous element or a parent element.
- predecessor: The previous element if the tree is flattened e.g.
break
is the predecessor ofx = 2
. - successor: The next element if the tree is flattened e.g.
x = 2
is the successor ofbreak
.
Use-case
I’m using this to contain an AST for compile-time evaluation in my personal WIP language.
Structs
- Roughly matches
std::collections::linked_list::Cursor
. - Roughly matches
std::collections::linked_list::CursorMut
. - An element in a [
OptionalNode
] with a known depth. - Iterates through elements depth-first in a [
OptionalNode
] returning references. - Iterates through elements depth-first in a [
OptionalNode
] returning mutable references. - A tree node.
- A cursor which can be used to mutate element, but only in such a way that it does not remove elements in
self.guarded_nodes
. This allows for a semi-mutable cursor on the upper portion of a syntax tree while maintaining a mutable cursor on the lower portion. - A doubly linked syntax tree.
Enums
- A statement in an AST may have:
Constants
- The string used for depth in the
SyntaxTree
std::fmt::Display
implementation.