Struct Tree

Source

pub struct Tree<T, F>where
    T: Copy,
    F: Flavor,
{ /* private fields */ }

Expand description

A syntax tree.

A tree is constructed through a Builder or by modifying an existing tree through a ChangeSet.

§Type parameters and bounds

The two type parameters of the tree determine the following properties:

T is the data stored in the tree.
F is the Flavor, declared with flavor!. Its Index determines the numerical bounds of spans, and if set to Empty the tree does not store any spans. Its Width determines the bounds of pointers in the tree, which decides how many nodes can be stored in it. It also selects the Storage used and its error type.

To use the default values, use the Builder::new constructor.

Implementations§

Source §

impl<T, F> Tree<T, F>
where T: Copy, F: Flavor,

Source

pub const fn span(&self) -> &Span<F::Index>

Get the span of the current node. The span of a node is the complete span of all its children.

§Examples

use syntree::Span;

let tree = syntree::tree! {
    "root" => {
        "number" => {
            ("lit", 5)
        },
        "ident" => {
            ("lit", 3)
        }
    },
    "root2" => {
        ("whitespace", 5)
    }
};

assert_eq!(tree.span(), Span::new(0, 13));

Source

pub fn len(&self) -> usize

The total number of elements in the tree.

§Examples

let mut tree: syntree::Builder<()> = syntree::Builder::new();
let tree = tree.build()?;

assert_eq!(tree.len(), 0);

let mut tree = syntree::tree! {
    "root" => {
        "child" => {
            ("token", 2)
        },
        ("whitespace", 1),
        "child2" => {}
    }
};

assert_eq!(tree.len(), 5);

Source

pub fn is_empty(&self) -> bool

Check if the current tree is empty. In that it doesn’t have any children at the root of the tree.

§Examples

let mut tree: syntree::Builder<()> = syntree::Builder::new();
let tree = tree.build()?;
assert!(tree.is_empty());

Source

pub fn capacity(&self) -> usize

Get the capacity of the tree.

§Examples

let mut tree: syntree::Builder<()> = syntree::Builder::new();
let tree = tree.build()?;

assert_eq!(tree.capacity(), 0);

let mut tree = syntree::tree! {
    "root" => {
        "child" => {
            ("token", 2)
        },
        ("whitespace", 1),
        "child2" => {}
    }
};

assert!(tree.capacity() >= 5);

Source

pub fn children(&self) -> Children<'_, T, F> ⓘ

Get all root nodes in the tree.

See Children for documentation.

Source

pub fn walk(&self) -> Walk<'_, T, F> ⓘ

Walk the tree forwards in a depth-first fashion visiting every node once.

See Walk for documentation.

Source

pub fn walk_events(&self) -> WalkEvents<'_, T, F> ⓘ

Walk the tree forwards in a depth-first fashion emitting events indicating how the tree is being traversed.

See WalkEvents for documentation.

Source

pub fn first(&self) -> Option<Node<'_, T, F>>

Get the first child node in the tree.

§Examples

let tree = syntree::tree! {
    "root" => {},
    "root2" => {}
};

let root = tree.first().ok_or("missing root")?;
assert_eq!(root.value(), "root");

Source

pub fn last(&self) -> Option<Node<'_, T, F>>

Get the last child node in the tree.

§Examples

let tree = syntree::tree! {
    "root" => {},
    "root2" => {}
};

let root = tree.last().ok_or("missing root")?;
assert_eq!(root.value(), "root2");

Source

pub fn get(&self, id: F::Pointer) -> Option<Node<'_, T, F>>

Get the node at the given index.

Note that an id might be re-used across different trees. This behavior is never unsafe, but is not well-defined.

§Examples

let tree = syntree::tree! {
    "root" => {
        "number" => {
            ("lit", 5)
        },
        "ident" => {
            ("lit", 3)
        }
    },
    "root2" => {
        ("whitespace", 5)
    }
};

let node = tree.first().and_then(|n| n.last()).ok_or("missing ident")?;
assert_eq!(node.value(), "ident");

let id = node.id();
let node = tree.get(id).ok_or("missing ident")?;
assert_eq!(node.value(), "ident");

Source

pub fn range(&self) -> Range<usize> ⓘ

Access the Span of the node as a Range.

§Examples

let tree = syntree::tree! {
    "root" => {
        "number" => {
            ("lit", 5)
        },
        "ident" => {
            ("lit", 3)
        }
    },
    "root2" => {
        ("whitespace", 5)
    }
};

assert_eq!(tree.range(), 0..13);

Source

pub fn node_with_range(&self, span: Range<usize>) -> Option<Node<'_, T, F>>

Query for the smallest node which contains the given Range.

A node contains the range when it starts at or before range.start, ends at or after range.end, and range.start lies before its end. Tokens are nodes too, so a range within a single token returns that token, however deeply it is nested.

Returns None if range.start > range.end, or if no node contains the range, such as one which spans two nodes at the root of the tree.
An empty range on the boundary between two tokens belongs to the token which starts there. An empty range at the end of the tree is contained by no node and returns None.
Only tokens with a non-empty span and their ancestors are considered, so empty nodes and empty tokens are never returned.

Tokens are looked up by binary search, which assumes they were added to the tree in non-decreasing order of their spans.

§Examples

let tree = syntree::tree! {
    "root" => {
        "child1" => {
            ("token1", 3)
        },
        "child2" => {
            "nested1" => {
                ("token2", 4),
            },
            ("token3", 1),
        },
        "child3" => {
            ("token4", 5)
        }
    },
    "root2" => {}
};

let node = tree.node_with_range(0..0).ok_or("missing 0")?;
assert_eq!(node.value(), "token1");

let node = tree.node_with_range(0..3).ok_or("missing 0..3")?;
assert_eq!(node.value(), "token1");

let node = tree.node_with_range(3..3).ok_or("missing 3")?;
assert_eq!(node.value(), "token2");

let node = tree.node_with_range(3..7).ok_or("missing 3..7")?;
assert_eq!(node.value(), "token2");
assert_eq!(node.parent().map(|n| n.value()), Some("nested1"));

let node = tree.node_with_range(7..8).ok_or("missing 7..8")?;
assert_eq!(node.value(), "token3");

let node = tree.node_with_range(3..8).ok_or("missing 3..8")?;
assert_eq!(node.value(), "child2");

let node = tree.node_with_range(8..13).ok_or("missing 8..13")?;
assert_eq!(node.value(), "token4");

let node = tree.node_with_range(2..4).ok_or("missing 2..4")?;
assert_eq!(node.value(), "root");

// The end of the tree, where the empty "root2" sits.
assert!(tree.node_with_range(13..13).is_none());
assert!(tree.node_with_range(0..14).is_none());
assert!(tree.node_with_range(4..2).is_none());

Range queries work as expected with checkpoints:

let mut tree = syntree::Builder::new();

let c = tree.checkpoint()?;
tree.open("child")?;
tree.token("lit", 3)?;
tree.close()?;
tree.close_at(&c, "root")?;
tree.token("sibling", 3)?;

let tree = tree.build()?;

let lit = tree.node_with_range(0..3).ok_or("missing at 0..3")?;
assert_eq!(lit.value(), "lit");
assert_eq!(lit.parent().map(|n| n.value()), Some("child"));

assert!(tree.node_with_range(2..4).is_none());

Source

pub fn node_with_span(&self, span: Span<F::Index>) -> Option<Node<'_, T, F>>

Query for the smallest node which contains the given Span.

This behaves like Tree::node_with_range: tokens are returned when they contain the span, and None is returned if span.start > span.end, if no node contains the span, or for an empty span at the end of the tree. Empty nodes and empty tokens are never returned.

Tokens are looked up by binary search, which assumes they were added to the tree in non-decreasing order of their spans.

§Examples

use syntree::Span;

let tree = syntree::tree! {
    "root" => {
        "child1" => {
            ("token1", 3)
        },
        "child2" => {
            "nested1" => {
                ("token2", 4),
            },
            ("token3", 1),
        },
        "child3" => {
            ("token4", 5)
        }
    },
    "root2" => {}
};

let node = tree.node_with_span(Span::point(0)).ok_or("missing 0")?;
assert_eq!(node.value(), "token1");

let node = tree.node_with_span(Span::new(0, 3)).ok_or("missing 0..3")?;
assert_eq!(node.value(), "token1");

let node = tree.node_with_span(Span::point(3)).ok_or("missing 3")?;
assert_eq!(node.value(), "token2");

let node = tree.node_with_span(Span::new(3, 7)).ok_or("missing 3..7")?;
assert_eq!(node.value(), "token2");

let node = tree.node_with_span(Span::new(7, 8)).ok_or("missing 7..8")?;
assert_eq!(node.value(), "token3");

let node = tree.node_with_span(Span::new(3, 8)).ok_or("missing 3..8")?;
assert_eq!(node.value(), "child2");

let node = tree.node_with_span(Span::new(8, 13)).ok_or("missing 8..13")?;
assert_eq!(node.value(), "token4");

let node = tree.node_with_span(Span::new(2, 4)).ok_or("missing 2..4")?;
assert_eq!(node.value(), "root");

assert!(tree.node_with_span(Span::point(13)).is_none());
assert!(tree.node_with_span(Span::new(4, 2)).is_none());

Range queries work as expected with checkpoints:

use syntree::{Span, Builder};

let mut tree = Builder::new();

let c = tree.checkpoint()?;

tree.open("child1")?;
tree.token("lit1", 3)?;
tree.close()?;

tree.open("child2")?;
tree.token("lit2", 2)?;
tree.close()?;

tree.close_at(&c, "root")?;

let tree = tree.build()?;

let node = tree.node_with_span(Span::point(0)).ok_or("missing at point 0")?;
assert_eq!(node.value(), "lit1");

let node = tree.node_with_span(Span::new(0, 3)).ok_or("missing at 0..3")?;
assert_eq!(node.value(), "lit1");
assert_eq!(node.parent().map(|n| n.value()), Some("child1"));

let node = tree.node_with_span(Span::point(3)).ok_or("missing at point 3")?;
assert_eq!(node.value(), "lit2");

let node = tree.node_with_span(Span::new(3, 5)).ok_or("missing at 3..5")?;
assert_eq!(node.value(), "lit2");

let node = tree.node_with_span(Span::new(2, 5)).ok_or("missing at 2..5")?;
assert_eq!(node.value(), "root");