pub struct Expander<K> { /* private fields */ }Expand description
Expands macro invocations and keeps the hygiene record of every expansion.
An expander owns three things:
- the hygiene table — every
Contextit has minted and the expansion that minted it, queried throughorigin; - a
Budget— limits on nesting depth, on the number of expansions, and on the number of tokens written, so that no macro, however hostile, can make the expander run forever or exhaust memory; and - pooled scratch buffers for matching and transcription, reused by every call so that steady-state expansion allocates only the output trees.
Use one expander for a whole compilation (or one per thread), so that every
context in the program comes from one table. The expander does not find
invocations or look macros up by name — that is the job of the language’s
expansion driver, which knows its syntax and scoping rules. The driver
finds an invocation, resolves the macro, calls expand
(or expand_at, when it tracks where each
invocation was found), splices the result back in, and repeats on the
output until no invocations remain.
§Examples
use macro_lang::{Context, Expander, Fragment, Macro, Pattern, Rule, Template, Tree};
use intern_lang::Interner;
use token_lang::Span;
let mut names = Interner::new();
let x = names.intern("x");
// twice!($x:tt) => $x $x
let twice = Macro::new(names.intern("twice"), vec![Rule {
pattern: vec![Pattern::Bind { name: x, fragment: Fragment::Tree }],
template: vec![Template::Var(x), Template::Var(x)],
}])?;
let mut expander = Expander::new();
let input = [Tree::token('a', Span::new(7, 8))];
let out = expander.expand(&twice, &input, Span::new(0, 9), Context::ROOT)?;
assert_eq!(out, vec![input[0].clone(), input[0].clone()]);Implementations§
Source§impl<K> Expander<K>
impl<K> Expander<K>
Sourcepub const DEFAULT_LIMIT: u32
pub const DEFAULT_LIMIT: u32
The recursion limit Expander::new uses: 128 nested expansions, the
same default as rustc’s recursion_limit. Equal to
Budget::DEFAULT.max_depth.
Sourcepub fn new() -> Self
pub fn new() -> Self
Creates an expander with the default budget: a
recursion limit of 128, 2^20 expansions, and
2^22 tokens.
§Examples
use macro_lang::{Budget, Expander};
let expander: Expander<char> = Expander::new();
assert_eq!(expander.limit(), Expander::<char>::DEFAULT_LIMIT);
assert_eq!(expander.budget(), Budget::DEFAULT);Sourcepub fn with_limit(limit: u32) -> Self
pub fn with_limit(limit: u32) -> Self
Creates an expander that allows invocations nested at most limit
expansions deep, with the rest of the default budget.
An invocation in source runs at depth 1. An invocation runs one level
deeper than the deepest expansion that produced its name token
(call_context) or any token of its input, and — through
expand_at — one level deeper than the code the
driver found it in. A macro that expands into a call of itself without
a base case therefore stops with ExpandError::RecursionLimit instead
of looping forever. A limit of 0 rejects every expansion.
§Examples
use macro_lang::Expander;
let expander: Expander<char> = Expander::with_limit(16);
assert_eq!(expander.limit(), 16);Sourcepub fn with_budget(budget: Budget) -> Self
pub fn with_budget(budget: Budget) -> Self
Creates an expander that enforces budget.
§Examples
use macro_lang::{Budget, Expander};
let budget = Budget::DEFAULT.with_max_expansions(10_000).with_max_tokens(100_000);
let expander: Expander<char> = Expander::with_budget(budget);
assert_eq!(expander.budget(), budget);Sourcepub const fn budget(&self) -> Budget
pub const fn budget(&self) -> Budget
Returns the budget this expander enforces.
§Examples
use macro_lang::{Budget, Expander};
assert_eq!(Expander::<char>::new().budget(), Budget::DEFAULT);
assert_eq!(Expander::<char>::with_limit(9).budget().max_depth, 9);Sourcepub fn set_budget(&mut self, budget: Budget)
pub fn set_budget(&mut self, budget: Budget)
Replaces the budget this expander enforces from now on.
Work already done stays counted: the expansion and token limits apply
to the usage accumulated since the expander was
created or last reset, so raising them lets
the current unit of work continue, and lowering them below what it has
already done makes every further expansion fail with
ExpandError::Budget.
§Examples
use macro_lang::{Budget, Context, ExpandError, Expander, Limit, Macro, Rule};
use intern_lang::Interner;
use token_lang::Span;
let mut names = Interner::new();
let empty = Macro::<char>::new(names.intern("empty"), vec![Rule {
pattern: vec![],
template: vec![],
}])?;
let mut expander = Expander::with_budget(Budget::DEFAULT.with_max_expansions(1));
assert!(expander.expand(&empty, &[], Span::new(0, 1), Context::ROOT).is_ok());
assert_eq!(
expander.expand(&empty, &[], Span::new(0, 1), Context::ROOT),
Err(ExpandError::Budget(Limit::Expansions { max: 1 })),
);
// Raising the budget lets the expander continue.
expander.set_budget(Budget::DEFAULT.with_max_expansions(2));
assert!(expander.expand(&empty, &[], Span::new(0, 1), Context::ROOT).is_ok());Sourcepub const fn usage(&self) -> Usage
pub const fn usage(&self) -> Usage
Returns the work charged against the budget since the expander was
created or reset_usage was last called:
the number of successful expansions and the tokens they wrote.
Failed expansions are never charged.
§Examples
use macro_lang::{Context, Expander, Macro, Rule, Template, Usage};
use intern_lang::Interner;
use token_lang::Span;
let mut names = Interner::new();
let s = Span::new(0, 1);
// three!() => a b c
let three = Macro::new(names.intern("three"), vec![Rule {
pattern: vec![],
template: "abc".chars().map(|c| Template::token(c, s)).collect(),
}])?;
let mut expander = Expander::new();
assert_eq!(expander.usage(), Usage::NONE);
expander.expand(&three, &[], s, Context::ROOT)?;
expander.expand(&three, &[], s, Context::ROOT)?;
assert_eq!(expander.usage().expansions, 2);
assert_eq!(expander.usage().tokens, 6);Sourcepub fn reset_usage(&mut self)
pub fn reset_usage(&mut self)
Zeroes the usage counters, giving the next unit
of work the full budget again.
A long-lived host — a language server, a REPL, a watch-mode compiler —
calls this once per unit of work: per document parse, per REPL entry,
per compilation. The budget then bounds each unit, not the host’s whole
lifetime. Nothing else changes: the budget itself, every context
already minted, and every Origin stay exactly as they were, so trees
produced before the reset remain valid.
Because minted contexts stay valid, the hygiene table is not shrunk:
it keeps a record for every expansion and every context minted since
the expander was created, so its memory grows with every expansion
whether or not usage is reset. A long-lived host should use one
expander per compilation (per document version in a language server)
and drop it along with the trees it produced, rather than keep one
expander for the whole session. An expander kept for billions of
expansions eventually reports ExpandError::ContextOverflow.
§Examples
use macro_lang::{Budget, Context, ExpandError, Expander, Limit, Macro, Rule, Template, Tree, Usage};
use intern_lang::Interner;
use token_lang::Span;
let mut names = Interner::new();
let s = Span::new(0, 1);
let one = Macro::new(names.intern("one"), vec![Rule {
pattern: vec![],
template: vec![Template::token('k', s)],
}])?;
// A REPL allowing two expansions per entry.
let mut expander = Expander::with_budget(Budget::DEFAULT.with_max_expansions(2));
let mut kept = Vec::new();
for _entry in 0..3 {
expander.reset_usage();
kept.extend(expander.expand(&one, &[], s, Context::ROOT)?);
kept.extend(expander.expand(&one, &[], s, Context::ROOT)?);
assert_eq!(
expander.expand(&one, &[], s, Context::ROOT),
Err(ExpandError::Budget(Limit::Expansions { max: 2 })),
);
}
assert_eq!(expander.usage().expansions, 2);
// Contexts minted before a reset still resolve.
let Some(Tree::Token { ctx, .. }) = kept.first() else {
return Err("expected a token".into());
};
assert!(expander.origin(*ctx).is_some());Sourcepub fn origin(&self, ctx: Context) -> Option<Origin>
pub fn origin(&self, ctx: Context) -> Option<Origin>
Reports which expansion minted ctx, or None for Context::ROOT and
for contexts this expander did not mint.
This is the query a name resolver and a diagnostic renderer need: the
Origin gives the context to fall back to for definition-site
resolution, the macro that introduced the token, and the invocation that
triggered it.
§Examples
use macro_lang::{Context, Expander, Macro, Rule, Template, Tree};
use intern_lang::Interner;
use token_lang::Span;
let mut names = Interner::new();
let make_tmp = names.intern("make_tmp");
let mac = Macro::new(make_tmp, vec![Rule {
pattern: vec![],
template: vec![Template::token('t', Span::new(40, 41))],
}])?;
let mut expander = Expander::new();
let out = expander.expand(&mac, &[], Span::new(3, 14), Context::ROOT)?;
let ctx = match out.first() {
Some(Tree::Token { ctx, .. }) => *ctx,
_ => return Err("expected one token".into()),
};
let origin = expander.origin(ctx).ok_or("context not minted by this expander")?;
assert_eq!(origin.macro_name, make_tmp);
assert_eq!(origin.call_site, Span::new(3, 14));
assert_eq!(expander.origin(Context::ROOT), None);Source§impl<K: Clone + PartialEq> Expander<K>
impl<K: Clone + PartialEq> Expander<K>
Sourcepub fn expand(
&mut self,
mac: &Macro<K>,
input: &[Tree<K>],
call_site: Span,
call_context: Context,
) -> Result<Vec<Tree<K>>, ExpandError>
pub fn expand( &mut self, mac: &Macro<K>, input: &[Tree<K>], call_site: Span, call_context: Context, ) -> Result<Vec<Tree<K>>, ExpandError>
Expands one invocation of mac.
The rules of mac are tried in order against input, and the first
rule whose pattern matches all of it is transcribed. Every literal token
the template writes receives a context minted for this expansion; every
captured tree is substituted with its contexts untouched.
This is expand_at with a depth of 0: the
invocation’s nesting depth is inferred from hygiene alone (see
with_limit). That inference cannot see an
invocation rebuilt entirely from tokens captured out of source — a
macro that writes $name ! ( $args ) from its own input reproduces a
call that is token-for-token identical to the one it came from. A
driver that knows where it found each invocation should call
expand_at, which bounds such a macro by the recursion limit; with
expand, the Budget’s expansion and token limits are what stop
it.
§Parameters
mac— the macro being invoked.input— the invocation’s argument trees: the contents between the invocation’s delimiters, without the delimiters themselves.call_site— the span of the whole invocation, recorded in theOriginof every minted context and used to report a mismatch on an empty invocation.call_context— the context of the invocation itself, normally the context of the macro-name token. PassContext::ROOTfor an invocation written in source; pass the token’s context for one produced by an earlier expansion, so that nesting depth is tracked.
§Errors
ExpandError::RecursionLimitif the invocation is nested deeper than the limit.ExpandError::Budgetif the expander has already performedBudget::max_expansionsexpansions, or if this one would take the number of tokens written pastBudget::max_tokens.ExpandError::NoMatchif no rule matches.ExpandError::Ambiguousif a rule matches in more than one way.ExpandError::RepetitionMismatchif a template repetition’s metavariables captured different numbers of trees.ExpandError::ContextOverflowif the context space is exhausted.
On error the expander is left exactly as it was.
§Examples
A vec-style macro: list!(a, b, c) expands to [a; b; c].
use macro_lang::{Context, Expander, Fragment, Kleene, Macro, Pattern, Rule, Template, Tree};
use intern_lang::Interner;
use token_lang::{Span, Token};
let mut names = Interner::new();
let e = names.intern("e");
let s = Span::new(0, 0); // spans of the definition, unimportant here
let list = Macro::new(names.intern("list"), vec![Rule {
pattern: vec![Pattern::Repeat {
body: vec![Pattern::Bind { name: e, fragment: Fragment::Tree }],
separator: Some(','),
kleene: Kleene::ZeroOrMore,
}],
template: vec![Template::Group {
open: Token::new('[', s),
close: Token::new(']', s),
body: vec![Template::Repeat {
body: vec![Template::Var(e)],
separator: Some(Token::new(';', s)),
}],
}],
}])?;
let input: Vec<Tree<char>> = "a,b,c"
.char_indices()
.map(|(i, c)| Tree::token(c, Span::new(i as u32, i as u32 + 1)))
.collect();
let mut expander = Expander::new();
let out = expander.expand(&list, &input, Span::new(0, 13), Context::ROOT)?;
let Some(Tree::Group { trees, .. }) = out.first() else {
return Err("expected one group".into());
};
let kinds: String = trees
.iter()
.filter_map(|t| match t { Tree::Token { token, .. } => Some(token.kind), _ => None })
.collect();
assert_eq!(kinds, "a;b;c");Sourcepub fn expand_at(
&mut self,
mac: &Macro<K>,
input: &[Tree<K>],
call_site: Span,
call_context: Context,
depth: u32,
) -> Result<Vec<Tree<K>>, ExpandError>
pub fn expand_at( &mut self, mac: &Macro<K>, input: &[Tree<K>], call_site: Span, call_context: Context, depth: u32, ) -> Result<Vec<Tree<K>>, ExpandError>
Expands one invocation of mac found in code nested depth expansions
deep.
Identical to expand, except that the driver also
says where it found the invocation: depth is 0 for an invocation
written in source, and d + 1 for one found in the output of a call
made with depth d. The invocation then runs at least one level deeper
than depth — deeper still if hygiene shows its name token or input was
produced further down — so the recursion limit bounds
every chain of nested expansions the driver performs, whatever the
macros write. That includes a macro that rebuilds its own invocation
from captured tokens, which expand alone cannot
tell apart from the original call.
§Parameters
As for expand, plus:
depth— the nesting depth of the code the invocation was found in.
§Errors
As for expand. On error the expander is left
exactly as it was.
§Examples
A driver that expands each output before splicing it threads the depth
through. Here again!($n:tt $b:tt) writes back exactly what it was
given, $n $b ( $n $b ) — a fresh invocation of itself made only of
captured tokens — and expand_at still stops it at the limit:
use macro_lang::{Context, ExpandError, Expander, Fragment, Macro, Pattern, Rule, Template, Tree};
use intern_lang::Interner;
use token_lang::{Span, Token};
let mut names = Interner::new();
let (n, b) = (names.intern("n"), names.intern("b"));
let tt = |name| Pattern::Bind { name, fragment: Fragment::Tree };
let s = Span::new(0, 1);
let again = Macro::new(names.intern("again"), vec![Rule {
pattern: vec![tt(n), tt(b)],
template: vec![
Template::Var(n),
Template::Var(b),
Template::Group {
open: Token::new('(', s),
close: Token::new(')', s),
body: vec![Template::Var(n), Template::Var(b)],
},
],
}])?;
let mut expander = Expander::with_limit(8);
// `a ! ( a ! )`, with `a` naming `again`: the arguments are the trees
// inside the group.
let mut args = vec![Tree::token('a', Span::new(7, 8)), Tree::token('!', Span::new(8, 9))];
let mut depth = 0;
let err = loop {
match expander.expand_at(&again, &args, s, Context::ROOT, depth) {
// The output is `again ! ( ... )` again: recurse into it.
Ok(out) => match out.get(2) {
Some(Tree::Group { trees, .. }) => {
args = trees.clone();
depth += 1;
}
_ => break None,
},
Err(err) => break Some(err),
}
};
assert_eq!(err, Some(ExpandError::RecursionLimit { limit: 8 }));