Skip to main content

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}