Expand description
§macro_lang
Hygienic macro expansion for language implementations: pattern matching over token trees, template substitution, and the hygiene bookkeeping that keeps a macro’s names from colliding with its caller’s.
This is the macro_rules! / Scheme syntax-rules model, generic over a
language’s token kind. A Macro is a list of Rules; each rule pairs a
Pattern that an invocation must match with a Template it expands to.
An Expander runs the expansion: it matches the invocation’s Trees
against each rule in turn, writes out the first matching template, and marks
every token the template introduces with a fresh hygiene Context.
The crate owns no syntax. A language’s front end lexes source into
token_lang tokens, groups them into Trees, lowers its own macro
definition syntax into patterns and templates, and drives expansion — finding
invocations, resolving macro names, and splicing results back in.
§Hygiene in one paragraph
Tokens written in source carry Context::ROOT. Each expansion mints a new
context for the literal tokens its template writes, while the trees it
substitutes from the invocation keep the context they arrived with. A name
resolver that treats two identifiers as the same binding only when both
spelling and context match then gets hygiene for free: a temporary the macro
introduces cannot capture a same-named variable passed in by the caller, and
cannot be captured by one. Expander::origin reports which expansion minted
a context, for definition-site fallback and for diagnostics.
§Example
A macro whose template introduces a temporary named t, invoked on input
that already contains a t. After expansion the two ts have equal
spelling but different contexts, so they can never be confused.
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");
// with_tmp!($x:tt) => t = $x
let with_tmp = Macro::new(names.intern("with_tmp"), vec![Rule {
pattern: vec![Pattern::Bind { name: x, fragment: Fragment::Tree }],
template: vec![
Template::token('t', Span::new(100, 101)),
Template::token('=', Span::new(102, 103)),
Template::Var(x),
],
}])?;
// with_tmp!(t) — the caller passes its own `t`.
let mut expander = Expander::new();
let input = [Tree::token('t', Span::new(9, 10))];
let out = expander.expand(&with_tmp, &input, Span::new(0, 11), Context::ROOT)?;
let contexts: Vec<Context> = out
.iter()
.filter_map(|tree| match tree {
Tree::Token { token, ctx } if token.kind == 't' => Some(*ctx),
_ => None,
})
.collect();
// The macro's `t` was minted a fresh context; the caller's `t` kept the root.
assert_eq!(contexts.len(), 2);
assert!(!contexts[0].is_root());
assert!(contexts[1].is_root());§Matching
Patterns are compiled into a nondeterministic automaton and simulated over the
input in a single left-to-right pass, merging parses that reach the same
point. Matching never backtracks, so its cost grows linearly with the input
(and polynomially with the pattern) even for adversarial input; and a rule
that matches in more than one way is reported as ExpandError::Ambiguous
instead of silently picking one parse.
§Bounded expansion
Macros are untrusted input, and a two-line macro can describe unbounded
work. Every expander enforces a Budget — a recursion limit, a cap on the
number of expansions, and a cap on the number of tokens written — with
defaults applied automatically, so a macro that recurses forever, doubles
its argument every round, or fans out into exponentially many calls stops
with ExpandError::RecursionLimit or ExpandError::Budget in bounded
time and memory. A driver that knows how deep each invocation sits passes
that depth to Expander::expand_at, which makes the recursion limit hold
even for a macro that rebuilds its own invocation from captured tokens.
§Features
std(default) — the standard library. Without it the crate is#![no_std]and needs onlyalloc; expansion uses no operating-system facilities either way.
§Stability
The public surface is frozen and stable as of 1.0.0: it follows Semantic
Versioning, with no breaking changes before 2.0. The full surface, the
matching and hygiene semantics that are part of the contract, and the SemVer
promise are catalogued in
docs/API.md.
Structs§
- Budget
- The limits an
Expanderenforces on the work it does. - Context
- The hygiene context of a token: which expansion, if any, introduced it.
- Expander
- Expands macro invocations and keeps the hygiene record of every expansion.
- Macro
- A validated, compiled macro: a name and an ordered list of rules.
- Origin
- Where a non-root
Contextcame from: the expansion that minted it. - Rule
- One arm of a macro: a pattern to match and the template it expands to.
- Usage
- The work an
Expanderhas charged against itsBudget: successful expansions and the tokens they wrote, since the expander was created orreset_usagewas last called.
Enums§
- Expand
Error - Why
Expander::expandcould not expand an invocation. - Fragment
- What a
Pattern::Bindmay capture: the fragment specifier. - Kleene
- How many times a
Pattern::Repeatmay match: the Kleene operator. - Limit
- Which part of a
Budgetan expansion ran out of, reported byExpandError::Budget. - Macro
Error - Why
Macro::newrejected a macro definition. - Pattern
- One element of a rule’s pattern — the left-hand side of a
macro_rules!arm. - Template
- One element of a rule’s template — the right-hand side of a
macro_rules!arm. - Tree
- A token tree: a single token, or a delimited group of trees.