Skip to main content

Tree

Enum Tree 

Source
pub enum Tree<K> {
    Token {
        token: Token<K>,
        ctx: Context,
    },
    Group {
        open: Token<K>,
        close: Token<K>,
        trees: Vec<Tree<K>>,
    },
}
Expand description

A token tree: a single token, or a delimited group of trees.

Macro expansion works on token trees rather than on a flat token stream or a finished syntax tree. Grouping by delimiters is the one piece of structure every language agrees on before parsing, and it is exactly the structure a pattern needs: a group is matched as a unit, and a fragment can capture a whole bracketed expression without knowing the grammar inside it. Expansion runs before parsing; the parser consumes the expanded trees.

K is the language’s token kind — the same type a lexer produces for token_lang::Token<K>. The crate only ever compares kinds for equality and clones them, so a small Copy kind (an enum carrying interned Symbols) is the fast path.

Every token carries its hygiene Context. Trees built from source use Context::ROOT, which is what Tree::token fills in.

§Examples

The token trees for f(a, b), using char as the token kind:

use macro_lang::Tree;
use token_lang::{Span, Token};

let call = vec![
    Tree::token('f', Span::new(0, 1)),
    Tree::Group {
        open: Token::new('(', Span::new(1, 2)),
        close: Token::new(')', Span::new(6, 7)),
        trees: vec![
            Tree::token('a', Span::new(2, 3)),
            Tree::token(',', Span::new(3, 4)),
            Tree::token('b', Span::new(5, 6)),
        ],
    },
];
assert_eq!(call[1].span(), Span::new(1, 7));

§Deeply nested trees

Clone, PartialEq and Hash walk a tree with a heap stack, so they work at any nesting depth, and so does everything the Expander does with the trees it is given and returns.

Dropping a tree and formatting it with Debug still recurse once per level of nesting, as for any recursive Rust type: Tree has public fields that callers move out of by value, so it cannot have a custom Drop without breaking them. A tree nested hundreds of thousands of groups deep (a few megabytes of ((((...)))) in hostile source) can overflow the stack when it is dropped. A front end that builds trees from untrusted text should either cap group nesting while it builds them, or hand finished trees to Tree::dismantle instead of dropping them.

Variants§

§

Token

A single token and its hygiene context.

Fields

§token: Token<K>

The token: its kind and source span.

§ctx: Context

The hygiene context the token belongs to.

§

Group

A delimited group: an opening token, the trees inside, and the closing token.

Fields

§open: Token<K>

The opening delimiter, such as (.

§close: Token<K>

The closing delimiter, such as ).

§trees: Vec<Tree<K>>

The trees between the delimiters, in source order.

Implementations§

Source§

impl<K> Tree<K>

Source

pub const fn token(kind: K, span: Span) -> Self

Builds a single-token tree in the root context — a token written directly in source.

§Examples
use macro_lang::{Context, Tree};
use token_lang::Span;

let tree = Tree::token('x', Span::new(4, 5));
assert!(matches!(
    tree,
    Tree::Token { token, ctx } if token.kind == 'x' && ctx == Context::ROOT
));
Source

pub const fn span(&self) -> Span

Returns the source span the tree covers.

For a token this is the token’s span; for a group it runs from the start of the opening delimiter to the end of the closing one.

§Examples
use macro_lang::Tree;
use token_lang::{Span, Token};

let group: Tree<char> = Tree::Group {
    open: Token::new('[', Span::new(10, 11)),
    close: Token::new(']', Span::new(14, 15)),
    trees: vec![],
};
assert_eq!(group.span(), Span::new(10, 15));
assert_eq!(Tree::token('x', Span::new(2, 3)).span(), Span::new(2, 3));
Source

pub fn dismantle(trees: impl IntoIterator<Item = Self>)

Drops trees without recursion, using a heap stack instead of the call stack.

An ordinary drop of a Tree recurses once per level of group nesting, so a tree nested hundreds of thousands of levels deep can overflow the stack. dismantle takes the tree apart one group at a time, so it is safe at any depth. It accepts anything that yields trees: one tree ([tree]), the Vec an expansion returns, or an iterator.

§Examples
use macro_lang::Tree;
use token_lang::{Span, Token};

// A million nested groups: dropping this normally would overflow.
let mut tree = Tree::token('x', Span::new(0, 1));
for _ in 0..1_000_000 {
    tree = Tree::Group {
        open: Token::new('(', Span::new(0, 1)),
        close: Token::new(')', Span::new(0, 1)),
        trees: vec![tree],
    };
}
Tree::dismantle([tree]);

Trait Implementations§

Source§

impl<K: Clone> Clone for Tree<K>

Source§

fn clone(&self) -> Self

Copies the tree with a heap stack, so any nesting depth is safe.

1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<K: Debug> Debug for Tree<K>

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<K: Eq> Eq for Tree<K>

Source§

impl<K: Hash> Hash for Tree<K>

Source§

fn hash<H: Hasher>(&self, state: &mut H)

Hashes the tree with a heap stack, so any nesting depth is safe. The values fed to the hasher are the ones a derived Hash would feed it, in the same order.

1.3.0 · Source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more
Source§

impl<K: PartialEq> PartialEq for Tree<K>

Source§

fn eq(&self, other: &Self) -> bool

Compares the trees with a heap stack, so any nesting depth is safe. Trees are equal when they have the same shape and every token, context and delimiter is equal.

1.0.0 (const: unstable) · Source§

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=. Read more

Auto Trait Implementations§

§

impl<K> Forget for Tree<K>

§

impl<K> Freeze for Tree<K>
where Token<K>: Freeze, Vec<Tree<K>>: Freeze,

§

impl<K> Move for Tree<K>

§

impl<K> RefUnwindSafe for Tree<K>

§

impl<K> Send for Tree<K>
where Token<K>: Send, Vec<Tree<K>>: Send,

§

impl<K> Sync for Tree<K>
where Token<K>: Sync, Vec<Tree<K>>: Sync,

§

impl<K> Unpin for Tree<K>
where Token<K>: Unpin, Vec<Tree<K>>: Unpin,

§

impl<K> UnsafeUnpin for Tree<K>

§

impl<K> UnwindSafe for Tree<K>

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.