macro_lang/tree.rs
1//! Token trees: the input and output of every expansion.
2
3use alloc::vec::Vec;
4use core::hash::{Hash, Hasher};
5use core::slice;
6
7use token_lang::{Span, Token};
8
9use crate::Context;
10
11/// A token tree: a single token, or a delimited group of trees.
12///
13/// Macro expansion works on token trees rather than on a flat token stream or a
14/// finished syntax tree. Grouping by delimiters is the one piece of structure
15/// every language agrees on before parsing, and it is exactly the structure
16/// a pattern needs: a group is matched as a unit, and a fragment can capture a
17/// whole bracketed expression without knowing the grammar inside it. Expansion
18/// runs before parsing; the parser consumes the expanded trees.
19///
20/// `K` is the language's token kind — the same type a lexer produces for
21/// `token_lang::Token<K>`. The crate only ever compares kinds for equality and
22/// clones them, so a small `Copy` kind (an `enum` carrying interned
23/// [`Symbol`](intern_lang::Symbol)s) is the fast path.
24///
25/// Every token carries its hygiene [`Context`]. Trees built from source use
26/// [`Context::ROOT`], which is what [`Tree::token`] fills in.
27///
28/// # Examples
29///
30/// The token trees for `f(a, b)`, using `char` as the token kind:
31///
32/// ```
33/// use macro_lang::Tree;
34/// use token_lang::{Span, Token};
35///
36/// let call = vec![
37/// Tree::token('f', Span::new(0, 1)),
38/// Tree::Group {
39/// open: Token::new('(', Span::new(1, 2)),
40/// close: Token::new(')', Span::new(6, 7)),
41/// trees: vec![
42/// Tree::token('a', Span::new(2, 3)),
43/// Tree::token(',', Span::new(3, 4)),
44/// Tree::token('b', Span::new(5, 6)),
45/// ],
46/// },
47/// ];
48/// assert_eq!(call[1].span(), Span::new(1, 7));
49/// ```
50///
51/// # Deeply nested trees
52///
53/// [`Clone`], [`PartialEq`] and [`Hash`] walk a tree with a heap stack, so
54/// they work at any nesting depth, and so does everything the
55/// [`Expander`](crate::Expander) does with the trees it is given and returns.
56///
57/// Dropping a tree and formatting it with [`Debug`] still recurse once per
58/// level of nesting, as for any recursive Rust type: `Tree` has public fields
59/// that callers move out of by value, so it cannot have a custom `Drop`
60/// without breaking them. A tree nested hundreds of thousands of groups deep
61/// (a few megabytes of `((((...))))` in hostile source) can overflow the stack
62/// when it is dropped. A front end that builds trees from untrusted text should
63/// either cap group nesting while it builds them, or hand finished trees to
64/// [`Tree::dismantle`] instead of dropping them.
65#[derive(Debug, Eq)]
66pub enum Tree<K> {
67 /// A single token and its hygiene context.
68 Token {
69 /// The token: its kind and source span.
70 token: Token<K>,
71 /// The hygiene context the token belongs to.
72 ctx: Context,
73 },
74 /// A delimited group: an opening token, the trees inside, and the closing
75 /// token.
76 Group {
77 /// The opening delimiter, such as `(`.
78 open: Token<K>,
79 /// The closing delimiter, such as `)`.
80 close: Token<K>,
81 /// The trees between the delimiters, in source order.
82 trees: Vec<Tree<K>>,
83 },
84}
85
86impl<K> Tree<K> {
87 /// Builds a single-token tree in the [root](Context::ROOT) context — a token
88 /// written directly in source.
89 ///
90 /// # Examples
91 ///
92 /// ```
93 /// use macro_lang::{Context, Tree};
94 /// use token_lang::Span;
95 ///
96 /// let tree = Tree::token('x', Span::new(4, 5));
97 /// assert!(matches!(
98 /// tree,
99 /// Tree::Token { token, ctx } if token.kind == 'x' && ctx == Context::ROOT
100 /// ));
101 /// ```
102 #[inline]
103 #[must_use]
104 pub const fn token(kind: K, span: Span) -> Self {
105 Self::Token {
106 token: Token::new(kind, span),
107 ctx: Context::ROOT,
108 }
109 }
110
111 /// Returns the source span the tree covers.
112 ///
113 /// For a token this is the token's span; for a group it runs from the start
114 /// of the opening delimiter to the end of the closing one.
115 ///
116 /// # Examples
117 ///
118 /// ```
119 /// use macro_lang::Tree;
120 /// use token_lang::{Span, Token};
121 ///
122 /// let group: Tree<char> = Tree::Group {
123 /// open: Token::new('[', Span::new(10, 11)),
124 /// close: Token::new(']', Span::new(14, 15)),
125 /// trees: vec![],
126 /// };
127 /// assert_eq!(group.span(), Span::new(10, 15));
128 /// assert_eq!(Tree::token('x', Span::new(2, 3)).span(), Span::new(2, 3));
129 /// ```
130 #[inline]
131 #[must_use]
132 pub const fn span(&self) -> Span {
133 match self {
134 Self::Token { token, .. } => token.span,
135 Self::Group { open, close, .. } => open.span.merge(close.span),
136 }
137 }
138
139 /// Drops `trees` without recursion, using a heap stack instead of the call
140 /// stack.
141 ///
142 /// An ordinary drop of a [`Tree`] recurses once per level of group nesting,
143 /// so a tree nested hundreds of thousands of levels deep can overflow the
144 /// stack. `dismantle` takes the tree apart one group at a time, so it is
145 /// safe at any depth. It accepts anything that yields trees: one tree
146 /// (`[tree]`), the `Vec` an expansion returns, or an iterator.
147 ///
148 /// # Examples
149 ///
150 /// ```
151 /// use macro_lang::Tree;
152 /// use token_lang::{Span, Token};
153 ///
154 /// // A million nested groups: dropping this normally would overflow.
155 /// let mut tree = Tree::token('x', Span::new(0, 1));
156 /// for _ in 0..1_000_000 {
157 /// tree = Tree::Group {
158 /// open: Token::new('(', Span::new(0, 1)),
159 /// close: Token::new(')', Span::new(0, 1)),
160 /// trees: vec![tree],
161 /// };
162 /// }
163 /// Tree::dismantle([tree]);
164 /// ```
165 pub fn dismantle(trees: impl IntoIterator<Item = Self>) {
166 let mut stack: Vec<Self> = trees.into_iter().collect();
167 while let Some(tree) = stack.pop() {
168 // Move the children out before the group itself is dropped, so
169 // every drop that happens here is of a tree with no children.
170 if let Self::Group { trees, .. } = tree {
171 stack.extend(trees);
172 }
173 }
174 }
175}
176
177/// One group being copied by [`Tree::clone`]: its delimiters, the originals
178/// still to copy, and the copies made so far.
179struct CloneFrame<'a, K> {
180 open: Token<K>,
181 close: Token<K>,
182 rest: slice::Iter<'a, Tree<K>>,
183 trees: Vec<Tree<K>>,
184}
185
186impl<'a, K: Clone> CloneFrame<'a, K> {
187 fn new(open: &Token<K>, close: &Token<K>, trees: &'a [Tree<K>]) -> Self {
188 Self {
189 open: open.clone(),
190 close: close.clone(),
191 rest: trees.iter(),
192 trees: Vec::with_capacity(trees.len()),
193 }
194 }
195}
196
197impl<K: Clone> Clone for Tree<K> {
198 /// Copies the tree with a heap stack, so any nesting depth is safe.
199 fn clone(&self) -> Self {
200 let (open, close, trees) = match self {
201 Self::Token { token, ctx } => {
202 return Self::Token {
203 token: token.clone(),
204 ctx: *ctx,
205 };
206 }
207 Self::Group { open, close, trees } => (open, close, trees),
208 };
209 let mut stack = Vec::new();
210 let mut frame = CloneFrame::new(open, close, trees);
211 loop {
212 match frame.rest.next() {
213 Some(Self::Token { token, ctx }) => frame.trees.push(Self::Token {
214 token: token.clone(),
215 ctx: *ctx,
216 }),
217 Some(Self::Group { open, close, trees }) => {
218 let child = CloneFrame::new(open, close, trees);
219 stack.push(core::mem::replace(&mut frame, child));
220 }
221 None => {
222 let done = Self::Group {
223 open: frame.open,
224 close: frame.close,
225 trees: frame.trees,
226 };
227 match stack.pop() {
228 Some(parent) => {
229 frame = parent;
230 frame.trees.push(done);
231 }
232 None => return done,
233 }
234 }
235 }
236 }
237 }
238}
239
240impl<K: PartialEq> PartialEq for Tree<K> {
241 /// Compares the trees with a heap stack, so any nesting depth is safe.
242 /// Trees are equal when they have the same shape and every token, context
243 /// and delimiter is equal.
244 fn eq(&self, other: &Self) -> bool {
245 let mut stack: Vec<(slice::Iter<'_, Self>, slice::Iter<'_, Self>)> = Vec::new();
246 let mut pair = (self, other);
247 loop {
248 match pair {
249 (
250 Self::Token { token, ctx },
251 Self::Token {
252 token: other_token,
253 ctx: other_ctx,
254 },
255 ) => {
256 if token != other_token || ctx != other_ctx {
257 return false;
258 }
259 }
260 (
261 Self::Group { open, close, trees },
262 Self::Group {
263 open: other_open,
264 close: other_close,
265 trees: other_trees,
266 },
267 ) => {
268 if open != other_open
269 || close != other_close
270 || trees.len() != other_trees.len()
271 {
272 return false;
273 }
274 stack.push((trees.iter(), other_trees.iter()));
275 }
276 _ => return false,
277 }
278 // The next pair of children to compare, from the innermost group
279 // that still has some.
280 loop {
281 let Some((left, right)) = stack.last_mut() else {
282 return true;
283 };
284 if let (Some(a), Some(b)) = (left.next(), right.next()) {
285 pair = (a, b);
286 break;
287 }
288 let _ = stack.pop();
289 }
290 }
291 }
292}
293
294impl<K: Hash> Hash for Tree<K> {
295 /// Hashes the tree with a heap stack, so any nesting depth is safe. The
296 /// values fed to the hasher are the ones a derived `Hash` would feed it,
297 /// in the same order.
298 fn hash<H: Hasher>(&self, state: &mut H) {
299 let mut stack: Vec<slice::Iter<'_, Self>> = Vec::new();
300 let mut next = Some(self);
301 while let Some(tree) = next {
302 match tree {
303 Self::Token { token, ctx } => {
304 state.write_isize(0);
305 token.hash(state);
306 ctx.hash(state);
307 }
308 Self::Group { open, close, trees } => {
309 state.write_isize(1);
310 open.hash(state);
311 close.hash(state);
312 state.write_usize(trees.len());
313 stack.push(trees.iter());
314 }
315 }
316 next = None;
317 while let Some(children) = stack.last_mut() {
318 if let Some(child) = children.next() {
319 next = Some(child);
320 break;
321 }
322 let _ = stack.pop();
323 }
324 }
325 }
326}
327
328#[cfg(test)]
329mod tests {
330 use alloc::vec;
331
332 use super::*;
333
334 #[test]
335 fn test_token_uses_root_context() {
336 let tree = Tree::token(1u8, Span::new(0, 1));
337 assert_eq!(
338 tree,
339 Tree::Token {
340 token: Token::new(1, Span::new(0, 1)),
341 ctx: Context::ROOT
342 }
343 );
344 }
345
346 #[test]
347 fn test_group_span_covers_both_delimiters() {
348 let tree = Tree::Group {
349 open: Token::new(0u8, Span::new(3, 4)),
350 close: Token::new(1u8, Span::new(9, 10)),
351 trees: vec![Tree::token(2u8, Span::new(5, 6))],
352 };
353 assert_eq!(tree.span(), Span::new(3, 10));
354 }
355}