Skip to main content

macro_lang/
budget.rs

1//! Resource budgets: how much work one expander may do before it refuses.
2//!
3//! Macro expansion is driven by input the compiler does not control, and a
4//! two-line macro can describe unbounded work. The recursion limit alone does
5//! not stop that: a macro that doubles its argument (`dup!($($t)*) =>
6//! dup!($($t)* $($t)*)`) reaches `2^128` tokens long before it reaches depth
7//! 128, and a macro that expands into two calls of itself performs `2^128`
8//! expansions without ever nesting deeper than 128. A [`Budget`] caps all three
9//! quantities, so the total time and memory an expander spends is bounded no
10//! matter what the macros say.
11
12use core::fmt;
13
14/// The limits an [`Expander`](crate::Expander) enforces on the work it does.
15///
16/// | Field | Limits | Default | Exceeding it reports |
17/// |---|---|---:|---|
18/// | [`max_depth`](Budget::max_depth) | How deeply invocations may nest. | 128 | [`ExpandError::RecursionLimit`](crate::ExpandError::RecursionLimit) |
19/// | [`max_expansions`](Budget::max_expansions) | Successful expansions since creation or the last `reset_usage`. | 1 048 576 (`2^20`) | [`ExpandError::Budget`](crate::ExpandError::Budget)`(`[`Limit::Expansions`]`)` |
20/// | [`max_tokens`](Budget::max_tokens) | Tokens written since creation or the last `reset_usage`. | 4 194 304 (`2^22`) | [`ExpandError::Budget`](crate::ExpandError::Budget)`(`[`Limit::Tokens`]`)` |
21///
22/// Every expander has a budget; [`Expander::new`](crate::Expander::new) uses
23/// [`Budget::DEFAULT`]. The expansion and token counts are **cumulative**: they
24/// accumulate in the expander's [`Usage`] until
25/// [`Expander::reset_usage`](crate::Expander::reset_usage) zeroes them. A
26/// batch compiler uses one expander per compilation and never resets, so the
27/// budget bounds the compilation's total macro output; a long-lived host (a
28/// language server, a REPL, a watch-mode compiler) resets once per unit of
29/// work — per document parse, per REPL entry, per compilation — so the budget
30/// bounds each unit instead of the host's lifetime.
31///
32/// The defaults are well above what typical programs expand to, and stop a
33/// runaway macro quickly: the doubling macro in `examples/budget` stops in
34/// about 0.2 s (release build) with a whole-process peak of about 400 MB.
35/// Memory grows in proportion to `max_tokens`, so lower it where that is too
36/// much; a unit of work that legitimately needs more can raise the budget with
37/// [`Expander::set_budget`](crate::Expander::set_budget).
38///
39/// Tokens are counted as they are written: one per token, two per group (its
40/// delimiters), and every token of a substituted capture. An expansion that
41/// would push the total past `max_tokens` stops as soon as it does, so even a
42/// single enormous expansion allocates no more than the budget allows.
43///
44/// A failed expansion is not charged: like every other error it leaves the
45/// expander exactly as it was.
46///
47/// The struct is `#[non_exhaustive]` so that further limits can be added in a
48/// minor release. Start from [`Budget::DEFAULT`] (or [`Budget::default`]) and
49/// adjust it with the `with_*` methods, or assign the public fields.
50///
51/// # Examples
52///
53/// ```
54/// use macro_lang::{Budget, Expander};
55///
56/// let budget = Budget::DEFAULT.with_max_depth(32).with_max_tokens(1 << 16);
57/// let expander: Expander<char> = Expander::with_budget(budget);
58/// assert_eq!(expander.budget().max_depth, 32);
59/// assert_eq!(expander.budget().max_tokens, 65_536);
60/// assert_eq!(expander.budget().max_expansions, Budget::DEFAULT.max_expansions);
61/// assert_eq!(expander.limit(), 32);
62/// ```
63#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
64#[non_exhaustive]
65pub struct Budget {
66    /// The deepest an invocation may be nested: an invocation in source runs at
67    /// depth 1, one produced by that expansion at depth 2, and so on. Exceeding
68    /// it reports [`ExpandError::RecursionLimit`](crate::ExpandError::RecursionLimit).
69    /// `0` rejects every expansion. This is the recursion limit that
70    /// [`Expander::with_limit`](crate::Expander::with_limit) sets.
71    pub max_depth: u32,
72    /// The number of successful expansions the expander may perform before
73    /// its [`Usage`] is [reset](crate::Expander::reset_usage). `0` rejects
74    /// every expansion.
75    pub max_expansions: usize,
76    /// The number of tokens the expander may write before its [`Usage`] is
77    /// [reset](crate::Expander::reset_usage), counting group delimiters and
78    /// substituted captures.
79    pub max_tokens: usize,
80}
81
82impl Budget {
83    /// The budget [`Expander::new`](crate::Expander::new) uses: depth 128 (the
84    /// same default as rustc's `recursion_limit`), `2^20` expansions, and
85    /// `2^22` tokens.
86    ///
87    /// # Examples
88    ///
89    /// ```
90    /// use macro_lang::Budget;
91    ///
92    /// assert_eq!(Budget::DEFAULT.max_depth, 128);
93    /// assert_eq!(Budget::DEFAULT.max_expansions, 1 << 20);
94    /// assert_eq!(Budget::DEFAULT.max_tokens, 1 << 22);
95    /// assert_eq!(Budget::default(), Budget::DEFAULT);
96    /// ```
97    pub const DEFAULT: Self = Self {
98        max_depth: 128,
99        max_expansions: 1 << 20,
100        max_tokens: 1 << 22,
101    };
102
103    /// Returns this budget with [`max_depth`](Budget::max_depth) replaced.
104    ///
105    /// # Examples
106    ///
107    /// ```
108    /// use macro_lang::Budget;
109    ///
110    /// assert_eq!(Budget::DEFAULT.with_max_depth(8).max_depth, 8);
111    /// ```
112    #[inline]
113    #[must_use]
114    pub const fn with_max_depth(mut self, max_depth: u32) -> Self {
115        self.max_depth = max_depth;
116        self
117    }
118
119    /// Returns this budget with [`max_expansions`](Budget::max_expansions)
120    /// replaced.
121    ///
122    /// # Examples
123    ///
124    /// ```
125    /// use macro_lang::Budget;
126    ///
127    /// assert_eq!(Budget::DEFAULT.with_max_expansions(10).max_expansions, 10);
128    /// ```
129    #[inline]
130    #[must_use]
131    pub const fn with_max_expansions(mut self, max_expansions: usize) -> Self {
132        self.max_expansions = max_expansions;
133        self
134    }
135
136    /// Returns this budget with [`max_tokens`](Budget::max_tokens) replaced.
137    ///
138    /// # Examples
139    ///
140    /// ```
141    /// use macro_lang::Budget;
142    ///
143    /// assert_eq!(Budget::DEFAULT.with_max_tokens(1000).max_tokens, 1000);
144    /// ```
145    #[inline]
146    #[must_use]
147    pub const fn with_max_tokens(mut self, max_tokens: usize) -> Self {
148        self.max_tokens = max_tokens;
149        self
150    }
151}
152
153impl Default for Budget {
154    /// Returns [`Budget::DEFAULT`].
155    fn default() -> Self {
156        Self::DEFAULT
157    }
158}
159
160/// The work an [`Expander`](crate::Expander) has charged against its
161/// [`Budget`]: successful expansions and the tokens they wrote, since the
162/// expander was created or
163/// [`reset_usage`](crate::Expander::reset_usage) was last called.
164///
165/// Returned by [`Expander::usage`](crate::Expander::usage). Failed expansions
166/// are never charged. The struct is `#[non_exhaustive]` so that further
167/// counters can be added in a minor release; read the fields directly.
168///
169/// Added in 1.1.0.
170///
171/// # Examples
172///
173/// ```
174/// use macro_lang::{Expander, Usage};
175///
176/// let expander: Expander<char> = Expander::new();
177/// let usage = expander.usage();
178/// assert_eq!((usage.expansions, usage.tokens), (0, 0));
179/// assert_eq!(usage, Usage::NONE);
180/// assert_eq!(Usage::default(), Usage::NONE);
181/// ```
182#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
183#[non_exhaustive]
184pub struct Usage {
185    /// Successful expansions, compared against
186    /// [`Budget::max_expansions`].
187    pub expansions: usize,
188    /// Tokens written by those expansions, counted as for
189    /// [`Budget::max_tokens`].
190    pub tokens: usize,
191}
192
193impl Usage {
194    /// No work done: both counters zero. What a new expander, and one just
195    /// [reset](crate::Expander::reset_usage), reports.
196    ///
197    /// # Examples
198    ///
199    /// ```
200    /// use macro_lang::Usage;
201    ///
202    /// assert_eq!(Usage::NONE.expansions, 0);
203    /// assert_eq!(Usage::NONE.tokens, 0);
204    /// ```
205    pub const NONE: Self = Self {
206        expansions: 0,
207        tokens: 0,
208    };
209}
210
211/// Which part of a [`Budget`] an expansion ran out of, reported by
212/// [`ExpandError::Budget`](crate::ExpandError::Budget).
213///
214/// Depth is not listed: exceeding [`Budget::max_depth`] keeps reporting
215/// [`ExpandError::RecursionLimit`](crate::ExpandError::RecursionLimit), as it
216/// did before budgets existed. The enum is `#[non_exhaustive]` so that further
217/// limits can be added in a minor release.
218///
219/// # Examples
220///
221/// ```
222/// use macro_lang::{Budget, Context, ExpandError, Expander, Limit, Macro, Rule, Template};
223/// use intern_lang::Interner;
224/// use token_lang::Span;
225///
226/// let mut names = Interner::new();
227/// // three!() => a b c
228/// let three = Macro::new(names.intern("three"), vec![Rule {
229///     pattern: vec![],
230///     template: "abc".chars().map(|c| Template::token(c, Span::new(0, 1))).collect(),
231/// }])?;
232///
233/// let mut expander = Expander::with_budget(Budget::DEFAULT.with_max_tokens(5));
234/// assert!(expander.expand(&three, &[], Span::new(0, 1), Context::ROOT).is_ok());
235/// // Three more tokens would make six, one more than the budget allows.
236/// assert_eq!(
237///     expander.expand(&three, &[], Span::new(0, 1), Context::ROOT),
238///     Err(ExpandError::Budget(Limit::Tokens { max: 5 })),
239/// );
240/// # Ok::<(), Box<dyn std::error::Error>>(())
241/// ```
242#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
243#[non_exhaustive]
244pub enum Limit {
245    /// [`Budget::max_expansions`] expansions have already been performed.
246    Expansions {
247        /// The limit that was reached.
248        max: usize,
249    },
250    /// The expansion would write more than [`Budget::max_tokens`] tokens in
251    /// total.
252    Tokens {
253        /// The limit that would have been exceeded.
254        max: usize,
255    },
256}
257
258impl fmt::Display for Limit {
259    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
260        match self {
261            Self::Expansions { max } => write!(f, "{max} expansions"),
262            Self::Tokens { max } => write!(f, "{max} output tokens"),
263        }
264    }
265}
266
267#[cfg(test)]
268mod tests {
269    use alloc::string::ToString;
270
271    use super::*;
272
273    #[test]
274    fn test_default_is_the_documented_budget() {
275        assert_eq!(Budget::default(), Budget::DEFAULT);
276        assert_eq!(Budget::DEFAULT.max_depth, 128);
277        assert_eq!(Budget::DEFAULT.max_expansions, 1_048_576);
278        assert_eq!(Budget::DEFAULT.max_tokens, 4_194_304);
279    }
280
281    #[test]
282    fn test_builders_replace_one_field_each() {
283        let budget = Budget::DEFAULT
284            .with_max_depth(3)
285            .with_max_expansions(4)
286            .with_max_tokens(5);
287        assert_eq!(
288            (budget.max_depth, budget.max_expansions, budget.max_tokens),
289            (3, 4, 5)
290        );
291        assert_eq!(
292            Budget::DEFAULT.with_max_tokens(9).max_expansions,
293            Budget::DEFAULT.max_expansions
294        );
295    }
296
297    #[test]
298    fn test_limit_display_names_the_quantity() {
299        assert_eq!(Limit::Expansions { max: 7 }.to_string(), "7 expansions");
300        assert_eq!(Limit::Tokens { max: 9 }.to_string(), "9 output tokens");
301    }
302}