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
Group
A delimited group: an opening token, the trees inside, and the closing token.
Implementations§
Source§impl<K> Tree<K>
impl<K> Tree<K>
Sourcepub const fn span(&self) -> Span
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));Sourcepub fn dismantle(trees: impl IntoIterator<Item = Self>)
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]);