Skip to main content

macro_lang/
expander.rs

1//! The expander: matching, transcription, the hygiene table, and the budget,
2//! in one place.
3
4use alloc::vec::Vec;
5use core::fmt;
6
7use token_lang::Span;
8
9use crate::context::Hygiene;
10use crate::matcher::{Matcher, Outcome};
11use crate::transcribe::{Expansion, Scratch, transcribe};
12use crate::{Budget, Context, ExpandError, Limit, Macro, Origin, Tree, Usage};
13
14/// Expands macro invocations and keeps the hygiene record of every expansion.
15///
16/// An expander owns three things:
17///
18/// - the **hygiene table** — every [`Context`] it has minted and the expansion
19///   that minted it, queried through [`origin`](Expander::origin);
20/// - a **[`Budget`]** — limits on nesting depth, on the number of expansions,
21///   and on the number of tokens written, so that no macro, however hostile,
22///   can make the expander run forever or exhaust memory; and
23/// - **pooled scratch buffers** for matching and transcription, reused by every
24///   call so that steady-state expansion allocates only the output trees.
25///
26/// Use one expander for a whole compilation (or one per thread), so that every
27/// context in the program comes from one table. The expander does not find
28/// invocations or look macros up by name — that is the job of the language's
29/// expansion driver, which knows its syntax and scoping rules. The driver
30/// finds an invocation, resolves the macro, calls [`expand`](Expander::expand)
31/// (or [`expand_at`](Expander::expand_at), when it tracks where each
32/// invocation was found), splices the result back in, and repeats on the
33/// output until no invocations remain.
34///
35/// # Examples
36///
37/// ```
38/// use macro_lang::{Context, Expander, Fragment, Macro, Pattern, Rule, Template, Tree};
39/// use intern_lang::Interner;
40/// use token_lang::Span;
41///
42/// let mut names = Interner::new();
43/// let x = names.intern("x");
44///
45/// // twice!($x:tt) => $x $x
46/// let twice = Macro::new(names.intern("twice"), vec![Rule {
47///     pattern: vec![Pattern::Bind { name: x, fragment: Fragment::Tree }],
48///     template: vec![Template::Var(x), Template::Var(x)],
49/// }])?;
50///
51/// let mut expander = Expander::new();
52/// let input = [Tree::token('a', Span::new(7, 8))];
53/// let out = expander.expand(&twice, &input, Span::new(0, 9), Context::ROOT)?;
54/// assert_eq!(out, vec![input[0].clone(), input[0].clone()]);
55/// # Ok::<(), Box<dyn std::error::Error>>(())
56/// ```
57pub struct Expander<K> {
58    hygiene: Hygiene,
59    matcher: Matcher<K>,
60    scratch: Scratch<K>,
61    budget: Budget,
62    /// The work charged against the budget since creation or the last
63    /// [`reset_usage`](Expander::reset_usage): successful expansions and the
64    /// tokens they wrote. Kept apart from the hygiene table, which is never
65    /// reset, so a host can start a fresh unit of work without invalidating
66    /// any context it has already handed out.
67    usage: Usage,
68}
69
70impl<K> Expander<K> {
71    /// The recursion limit [`Expander::new`] uses: 128 nested expansions, the
72    /// same default as rustc's `recursion_limit`. Equal to
73    /// [`Budget::DEFAULT`]`.max_depth`.
74    pub const DEFAULT_LIMIT: u32 = Budget::DEFAULT.max_depth;
75
76    /// Creates an expander with the [default budget](Budget::DEFAULT): a
77    /// recursion limit of [128](Self::DEFAULT_LIMIT), `2^20` expansions, and
78    /// `2^22` tokens.
79    ///
80    /// # Examples
81    ///
82    /// ```
83    /// use macro_lang::{Budget, Expander};
84    ///
85    /// let expander: Expander<char> = Expander::new();
86    /// assert_eq!(expander.limit(), Expander::<char>::DEFAULT_LIMIT);
87    /// assert_eq!(expander.budget(), Budget::DEFAULT);
88    /// ```
89    #[must_use]
90    pub fn new() -> Self {
91        Self::with_budget(Budget::DEFAULT)
92    }
93
94    /// Creates an expander that allows invocations nested at most `limit`
95    /// expansions deep, with the rest of the [default budget](Budget::DEFAULT).
96    ///
97    /// An invocation in source runs at depth 1. An invocation runs one level
98    /// deeper than the deepest expansion that produced its name token
99    /// (`call_context`) or any token of its input, and — through
100    /// [`expand_at`](Expander::expand_at) — one level deeper than the code the
101    /// driver found it in. A macro that expands into a call of itself without
102    /// a base case therefore stops with [`ExpandError::RecursionLimit`] instead
103    /// of looping forever. A limit of `0` rejects every expansion.
104    ///
105    /// # Examples
106    ///
107    /// ```
108    /// use macro_lang::Expander;
109    ///
110    /// let expander: Expander<char> = Expander::with_limit(16);
111    /// assert_eq!(expander.limit(), 16);
112    /// ```
113    #[must_use]
114    pub fn with_limit(limit: u32) -> Self {
115        Self::with_budget(Budget::DEFAULT.with_max_depth(limit))
116    }
117
118    /// Creates an expander that enforces `budget`.
119    ///
120    /// # Examples
121    ///
122    /// ```
123    /// use macro_lang::{Budget, Expander};
124    ///
125    /// let budget = Budget::DEFAULT.with_max_expansions(10_000).with_max_tokens(100_000);
126    /// let expander: Expander<char> = Expander::with_budget(budget);
127    /// assert_eq!(expander.budget(), budget);
128    /// ```
129    #[must_use]
130    pub fn with_budget(budget: Budget) -> Self {
131        Self {
132            hygiene: Hygiene::default(),
133            matcher: Matcher::default(),
134            scratch: Scratch::default(),
135            budget,
136            usage: Usage::NONE,
137        }
138    }
139
140    /// Returns the recursion limit: the budget's
141    /// [`max_depth`](Budget::max_depth).
142    ///
143    /// # Examples
144    ///
145    /// ```
146    /// use macro_lang::Expander;
147    ///
148    /// assert_eq!(Expander::<char>::with_limit(4).limit(), 4);
149    /// ```
150    #[inline]
151    #[must_use]
152    pub const fn limit(&self) -> u32 {
153        self.budget.max_depth
154    }
155
156    /// Returns the budget this expander enforces.
157    ///
158    /// # Examples
159    ///
160    /// ```
161    /// use macro_lang::{Budget, Expander};
162    ///
163    /// assert_eq!(Expander::<char>::new().budget(), Budget::DEFAULT);
164    /// assert_eq!(Expander::<char>::with_limit(9).budget().max_depth, 9);
165    /// ```
166    #[inline]
167    #[must_use]
168    pub const fn budget(&self) -> Budget {
169        self.budget
170    }
171
172    /// Replaces the budget this expander enforces from now on.
173    ///
174    /// Work already done stays counted: the expansion and token limits apply
175    /// to the [`usage`](Expander::usage) accumulated since the expander was
176    /// created or last [reset](Expander::reset_usage), so raising them lets
177    /// the current unit of work continue, and lowering them below what it has
178    /// already done makes every further expansion fail with
179    /// [`ExpandError::Budget`].
180    ///
181    /// # Examples
182    ///
183    /// ```
184    /// use macro_lang::{Budget, Context, ExpandError, Expander, Limit, Macro, Rule};
185    /// use intern_lang::Interner;
186    /// use token_lang::Span;
187    ///
188    /// let mut names = Interner::new();
189    /// let empty = Macro::<char>::new(names.intern("empty"), vec![Rule {
190    ///     pattern: vec![],
191    ///     template: vec![],
192    /// }])?;
193    ///
194    /// let mut expander = Expander::with_budget(Budget::DEFAULT.with_max_expansions(1));
195    /// assert!(expander.expand(&empty, &[], Span::new(0, 1), Context::ROOT).is_ok());
196    /// assert_eq!(
197    ///     expander.expand(&empty, &[], Span::new(0, 1), Context::ROOT),
198    ///     Err(ExpandError::Budget(Limit::Expansions { max: 1 })),
199    /// );
200    ///
201    /// // Raising the budget lets the expander continue.
202    /// expander.set_budget(Budget::DEFAULT.with_max_expansions(2));
203    /// assert!(expander.expand(&empty, &[], Span::new(0, 1), Context::ROOT).is_ok());
204    /// # Ok::<(), Box<dyn std::error::Error>>(())
205    /// ```
206    #[inline]
207    pub fn set_budget(&mut self, budget: Budget) {
208        self.budget = budget;
209    }
210
211    /// Returns the work charged against the budget since the expander was
212    /// created or [`reset_usage`](Expander::reset_usage) was last called:
213    /// the number of successful expansions and the tokens they wrote.
214    ///
215    /// Failed expansions are never charged.
216    ///
217    /// # Examples
218    ///
219    /// ```
220    /// use macro_lang::{Context, Expander, Macro, Rule, Template, Usage};
221    /// use intern_lang::Interner;
222    /// use token_lang::Span;
223    ///
224    /// let mut names = Interner::new();
225    /// let s = Span::new(0, 1);
226    /// // three!() => a b c
227    /// let three = Macro::new(names.intern("three"), vec![Rule {
228    ///     pattern: vec![],
229    ///     template: "abc".chars().map(|c| Template::token(c, s)).collect(),
230    /// }])?;
231    ///
232    /// let mut expander = Expander::new();
233    /// assert_eq!(expander.usage(), Usage::NONE);
234    /// expander.expand(&three, &[], s, Context::ROOT)?;
235    /// expander.expand(&three, &[], s, Context::ROOT)?;
236    /// assert_eq!(expander.usage().expansions, 2);
237    /// assert_eq!(expander.usage().tokens, 6);
238    /// # Ok::<(), Box<dyn std::error::Error>>(())
239    /// ```
240    #[inline]
241    #[must_use]
242    pub const fn usage(&self) -> Usage {
243        self.usage
244    }
245
246    /// Zeroes the [`usage`](Expander::usage) counters, giving the next unit
247    /// of work the full budget again.
248    ///
249    /// A long-lived host — a language server, a REPL, a watch-mode compiler —
250    /// calls this once per unit of work: per document parse, per REPL entry,
251    /// per compilation. The budget then bounds each unit, not the host's whole
252    /// lifetime. Nothing else changes: the budget itself, every context
253    /// already minted, and every [`Origin`] stay exactly as they were, so trees
254    /// produced before the reset remain valid.
255    ///
256    /// Because minted contexts stay valid, the hygiene table is not shrunk:
257    /// it keeps a record for every expansion and every context minted since
258    /// the expander was created, so its memory grows with every expansion
259    /// whether or not usage is reset. A long-lived host should use one
260    /// expander per compilation (per document version in a language server)
261    /// and drop it along with the trees it produced, rather than keep one
262    /// expander for the whole session. An expander kept for billions of
263    /// expansions eventually reports [`ExpandError::ContextOverflow`].
264    ///
265    /// # Examples
266    ///
267    /// ```
268    /// use macro_lang::{Budget, Context, ExpandError, Expander, Limit, Macro, Rule, Template, Tree, Usage};
269    /// use intern_lang::Interner;
270    /// use token_lang::Span;
271    ///
272    /// let mut names = Interner::new();
273    /// let s = Span::new(0, 1);
274    /// let one = Macro::new(names.intern("one"), vec![Rule {
275    ///     pattern: vec![],
276    ///     template: vec![Template::token('k', s)],
277    /// }])?;
278    ///
279    /// // A REPL allowing two expansions per entry.
280    /// let mut expander = Expander::with_budget(Budget::DEFAULT.with_max_expansions(2));
281    /// let mut kept = Vec::new();
282    /// for _entry in 0..3 {
283    ///     expander.reset_usage();
284    ///     kept.extend(expander.expand(&one, &[], s, Context::ROOT)?);
285    ///     kept.extend(expander.expand(&one, &[], s, Context::ROOT)?);
286    ///     assert_eq!(
287    ///         expander.expand(&one, &[], s, Context::ROOT),
288    ///         Err(ExpandError::Budget(Limit::Expansions { max: 2 })),
289    ///     );
290    /// }
291    /// assert_eq!(expander.usage().expansions, 2);
292    ///
293    /// // Contexts minted before a reset still resolve.
294    /// let Some(Tree::Token { ctx, .. }) = kept.first() else {
295    ///     return Err("expected a token".into());
296    /// };
297    /// assert!(expander.origin(*ctx).is_some());
298    /// # Ok::<(), Box<dyn std::error::Error>>(())
299    /// ```
300    #[inline]
301    pub fn reset_usage(&mut self) {
302        self.usage = Usage::NONE;
303    }
304
305    /// Reports which expansion minted `ctx`, or `None` for [`Context::ROOT`] and
306    /// for contexts this expander did not mint.
307    ///
308    /// This is the query a name resolver and a diagnostic renderer need: the
309    /// [`Origin`] gives the context to fall back to for definition-site
310    /// resolution, the macro that introduced the token, and the invocation that
311    /// triggered it.
312    ///
313    /// # Examples
314    ///
315    /// ```
316    /// use macro_lang::{Context, Expander, Macro, Rule, Template, Tree};
317    /// use intern_lang::Interner;
318    /// use token_lang::Span;
319    ///
320    /// let mut names = Interner::new();
321    /// let make_tmp = names.intern("make_tmp");
322    /// let mac = Macro::new(make_tmp, vec![Rule {
323    ///     pattern: vec![],
324    ///     template: vec![Template::token('t', Span::new(40, 41))],
325    /// }])?;
326    ///
327    /// let mut expander = Expander::new();
328    /// let out = expander.expand(&mac, &[], Span::new(3, 14), Context::ROOT)?;
329    /// let ctx = match out.first() {
330    ///     Some(Tree::Token { ctx, .. }) => *ctx,
331    ///     _ => return Err("expected one token".into()),
332    /// };
333    ///
334    /// let origin = expander.origin(ctx).ok_or("context not minted by this expander")?;
335    /// assert_eq!(origin.macro_name, make_tmp);
336    /// assert_eq!(origin.call_site, Span::new(3, 14));
337    /// assert_eq!(expander.origin(Context::ROOT), None);
338    /// # Ok::<(), Box<dyn std::error::Error>>(())
339    /// ```
340    #[inline]
341    #[must_use]
342    pub fn origin(&self, ctx: Context) -> Option<Origin> {
343        self.hygiene.origin(ctx)
344    }
345}
346
347impl<K: Clone + PartialEq> Expander<K> {
348    /// Expands one invocation of `mac`.
349    ///
350    /// The rules of `mac` are tried in order against `input`, and the first
351    /// rule whose pattern matches all of it is transcribed. Every literal token
352    /// the template writes receives a context minted for this expansion; every
353    /// captured tree is substituted with its contexts untouched.
354    ///
355    /// This is [`expand_at`](Expander::expand_at) with a depth of `0`: the
356    /// invocation's nesting depth is inferred from hygiene alone (see
357    /// [`with_limit`](Expander::with_limit)). That inference cannot see an
358    /// invocation rebuilt entirely from tokens captured out of source — a
359    /// macro that writes `$name ! ( $args )` from its own input reproduces a
360    /// call that is token-for-token identical to the one it came from. A
361    /// driver that knows where it found each invocation should call
362    /// `expand_at`, which bounds such a macro by the recursion limit; with
363    /// `expand`, the [`Budget`]'s expansion and token limits are what stop
364    /// it.
365    ///
366    /// # Parameters
367    ///
368    /// - `mac` — the macro being invoked.
369    /// - `input` — the invocation's argument trees: the contents between the
370    ///   invocation's delimiters, without the delimiters themselves.
371    /// - `call_site` — the span of the whole invocation, recorded in the
372    ///   [`Origin`] of every minted context and used to report a mismatch on an
373    ///   empty invocation.
374    /// - `call_context` — the context of the invocation itself, normally the
375    ///   context of the macro-name token. Pass [`Context::ROOT`] for an
376    ///   invocation written in source; pass the token's context for one produced
377    ///   by an earlier expansion, so that nesting depth is tracked.
378    ///
379    /// # Errors
380    ///
381    /// - [`ExpandError::RecursionLimit`] if the invocation is nested deeper than
382    ///   the [limit](Expander::limit).
383    /// - [`ExpandError::Budget`] if the expander has already performed
384    ///   [`Budget::max_expansions`] expansions, or if this one would take the
385    ///   number of tokens written past [`Budget::max_tokens`].
386    /// - [`ExpandError::NoMatch`] if no rule matches.
387    /// - [`ExpandError::Ambiguous`] if a rule matches in more than one way.
388    /// - [`ExpandError::RepetitionMismatch`] if a template repetition's
389    ///   metavariables captured different numbers of trees.
390    /// - [`ExpandError::ContextOverflow`] if the context space is exhausted.
391    ///
392    /// On error the expander is left exactly as it was.
393    ///
394    /// # Examples
395    ///
396    /// A `vec`-style macro: `list!(a, b, c)` expands to `[a; b; c]`.
397    ///
398    /// ```
399    /// use macro_lang::{Context, Expander, Fragment, Kleene, Macro, Pattern, Rule, Template, Tree};
400    /// use intern_lang::Interner;
401    /// use token_lang::{Span, Token};
402    ///
403    /// let mut names = Interner::new();
404    /// let e = names.intern("e");
405    /// let s = Span::new(0, 0); // spans of the definition, unimportant here
406    /// let list = Macro::new(names.intern("list"), vec![Rule {
407    ///     pattern: vec![Pattern::Repeat {
408    ///         body: vec![Pattern::Bind { name: e, fragment: Fragment::Tree }],
409    ///         separator: Some(','),
410    ///         kleene: Kleene::ZeroOrMore,
411    ///     }],
412    ///     template: vec![Template::Group {
413    ///         open: Token::new('[', s),
414    ///         close: Token::new(']', s),
415    ///         body: vec![Template::Repeat {
416    ///             body: vec![Template::Var(e)],
417    ///             separator: Some(Token::new(';', s)),
418    ///         }],
419    ///     }],
420    /// }])?;
421    ///
422    /// let input: Vec<Tree<char>> = "a,b,c"
423    ///     .char_indices()
424    ///     .map(|(i, c)| Tree::token(c, Span::new(i as u32, i as u32 + 1)))
425    ///     .collect();
426    /// let mut expander = Expander::new();
427    /// let out = expander.expand(&list, &input, Span::new(0, 13), Context::ROOT)?;
428    ///
429    /// let Some(Tree::Group { trees, .. }) = out.first() else {
430    ///     return Err("expected one group".into());
431    /// };
432    /// let kinds: String = trees
433    ///     .iter()
434    ///     .filter_map(|t| match t { Tree::Token { token, .. } => Some(token.kind), _ => None })
435    ///     .collect();
436    /// assert_eq!(kinds, "a;b;c");
437    /// # Ok::<(), Box<dyn std::error::Error>>(())
438    /// ```
439    #[inline]
440    pub fn expand(
441        &mut self,
442        mac: &Macro<K>,
443        input: &[Tree<K>],
444        call_site: Span,
445        call_context: Context,
446    ) -> Result<Vec<Tree<K>>, ExpandError> {
447        self.expand_at(mac, input, call_site, call_context, 0)
448    }
449
450    /// Expands one invocation of `mac` found in code nested `depth` expansions
451    /// deep.
452    ///
453    /// Identical to [`expand`](Expander::expand), except that the driver also
454    /// says where it found the invocation: `depth` is `0` for an invocation
455    /// written in source, and `d + 1` for one found in the output of a call
456    /// made with depth `d`. The invocation then runs at least one level deeper
457    /// than `depth` — deeper still if hygiene shows its name token or input was
458    /// produced further down — so the [recursion limit](Expander::limit) bounds
459    /// every chain of nested expansions the driver performs, whatever the
460    /// macros write. That includes a macro that rebuilds its own invocation
461    /// from captured tokens, which [`expand`](Expander::expand) alone cannot
462    /// tell apart from the original call.
463    ///
464    /// # Parameters
465    ///
466    /// As for [`expand`](Expander::expand), plus:
467    ///
468    /// - `depth` — the nesting depth of the code the invocation was found in.
469    ///
470    /// # Errors
471    ///
472    /// As for [`expand`](Expander::expand). On error the expander is left
473    /// exactly as it was.
474    ///
475    /// # Examples
476    ///
477    /// A driver that expands each output before splicing it threads the depth
478    /// through. Here `again!($n:tt $b:tt)` writes back exactly what it was
479    /// given, `$n $b ( $n $b )` — a fresh invocation of itself made only of
480    /// captured tokens — and `expand_at` still stops it at the limit:
481    ///
482    /// ```
483    /// use macro_lang::{Context, ExpandError, Expander, Fragment, Macro, Pattern, Rule, Template, Tree};
484    /// use intern_lang::Interner;
485    /// use token_lang::{Span, Token};
486    ///
487    /// let mut names = Interner::new();
488    /// let (n, b) = (names.intern("n"), names.intern("b"));
489    /// let tt = |name| Pattern::Bind { name, fragment: Fragment::Tree };
490    /// let s = Span::new(0, 1);
491    /// let again = Macro::new(names.intern("again"), vec![Rule {
492    ///     pattern: vec![tt(n), tt(b)],
493    ///     template: vec![
494    ///         Template::Var(n),
495    ///         Template::Var(b),
496    ///         Template::Group {
497    ///             open: Token::new('(', s),
498    ///             close: Token::new(')', s),
499    ///             body: vec![Template::Var(n), Template::Var(b)],
500    ///         },
501    ///     ],
502    /// }])?;
503    ///
504    /// let mut expander = Expander::with_limit(8);
505    /// // `a ! ( a ! )`, with `a` naming `again`: the arguments are the trees
506    /// // inside the group.
507    /// let mut args = vec![Tree::token('a', Span::new(7, 8)), Tree::token('!', Span::new(8, 9))];
508    /// let mut depth = 0;
509    /// let err = loop {
510    ///     match expander.expand_at(&again, &args, s, Context::ROOT, depth) {
511    ///         // The output is `again ! ( ... )` again: recurse into it.
512    ///         Ok(out) => match out.get(2) {
513    ///             Some(Tree::Group { trees, .. }) => {
514    ///                 args = trees.clone();
515    ///                 depth += 1;
516    ///             }
517    ///             _ => break None,
518    ///         },
519    ///         Err(err) => break Some(err),
520    ///     }
521    /// };
522    /// assert_eq!(err, Some(ExpandError::RecursionLimit { limit: 8 }));
523    /// # Ok::<(), Box<dyn std::error::Error>>(())
524    /// ```
525    pub fn expand_at(
526        &mut self,
527        mac: &Macro<K>,
528        input: &[Tree<K>],
529        call_site: Span,
530        call_context: Context,
531        depth: u32,
532    ) -> Result<Vec<Tree<K>>, ExpandError> {
533        self.matcher.load(input);
534        let depth = self.depth_of(call_context, depth).saturating_add(1);
535        if depth > self.budget.max_depth {
536            return Err(ExpandError::RecursionLimit {
537                limit: self.budget.max_depth,
538            });
539        }
540        if self.usage.expansions >= self.budget.max_expansions {
541            return Err(ExpandError::Budget(Limit::Expansions {
542                max: self.budget.max_expansions,
543            }));
544        }
545
546        let mut furthest = 0;
547        for (index, rule) in mac.rules().iter().enumerate() {
548            match self.matcher.run(rule) {
549                Outcome::Match => {
550                    let checkpoint = self.hygiene.checkpoint();
551                    let expansion = self
552                        .hygiene
553                        .begin(mac.name(), call_site, call_context, depth);
554                    let result = transcribe(
555                        Expansion {
556                            rule,
557                            index,
558                            matcher: &self.matcher,
559                            hygiene: &mut self.hygiene,
560                            expansion,
561                            tokens_left: self.budget.max_tokens.saturating_sub(self.usage.tokens),
562                            tokens_max: self.budget.max_tokens,
563                        },
564                        &mut self.scratch,
565                    );
566                    return match result {
567                        Ok((out, written)) => {
568                            self.usage.tokens = self.usage.tokens.saturating_add(written);
569                            self.usage.expansions = self.usage.expansions.saturating_add(1);
570                            Ok(out)
571                        }
572                        Err(err) => {
573                            self.hygiene.rollback(checkpoint);
574                            Err(err)
575                        }
576                    };
577                }
578                Outcome::Ambiguous => return Err(ExpandError::Ambiguous { rule: index }),
579                Outcome::NoMatch { furthest: reached } => furthest = furthest.max(reached),
580            }
581        }
582        Err(ExpandError::NoMatch {
583            span: self.matcher.span_at(furthest, call_site),
584        })
585    }
586
587    /// The depth of the code the loaded invocation belongs to: the deepest of
588    /// the driver's `depth`, the expansion that produced the name token, and
589    /// the expansions that produced any token of the input.
590    ///
591    /// Counting the input closes the gap a name token alone leaves: a macro
592    /// that rebuilds its own invocation around a captured name still writes
593    /// its own literal tokens into the arguments, and those carry its depth.
594    fn depth_of(&self, call_context: Context, depth: u32) -> u32 {
595        let mut deepest = depth.max(self.hygiene.depth(call_context));
596        if self.matcher.marked {
597            // Runs of tokens share a context, so look each run up once.
598            let mut last = Context::ROOT;
599            for ctx in self.matcher.contexts() {
600                if ctx != last {
601                    deepest = deepest.max(self.hygiene.depth(ctx));
602                    last = ctx;
603                }
604            }
605        }
606        deepest
607    }
608}
609
610impl<K> Default for Expander<K> {
611    fn default() -> Self {
612        Self::new()
613    }
614}
615
616impl<K> fmt::Debug for Expander<K> {
617    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
618        let (contexts, expansions) = self.hygiene.sizes();
619        f.debug_struct("Expander")
620            .field("limit", &self.budget.max_depth)
621            .field("contexts", &contexts)
622            .field("expansions", &expansions)
623            .finish()
624    }
625}