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 of x = -10.
  • previous: x = -10 is the previous element of loop.
  • child: x = x + 1 is the child element of loop.
  • parent: loop is the parent element of x = 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 of x = 2.
  • successor: The next element if the tree is flattened e.g. x = 2 is the successor of break.

Use-case

I’m using this to contain an AST for compile-time evaluation in my personal WIP language.

Structs

Enums

Constants