The model
A handful of plain-data types and one engine:
- A
Treeis a token tree: a single token, or a delimited group of trees. Invocations go in as trees and expansions come out as trees. - A
Rulepairs aPattern(what an invocation must look like) with aTemplate(what it expands to). Patterns bind metavariables —$x:tt— and repeat —$( ... ),*; templates substitute and repeat them. - A
Macrois a name and an ordered list of rules, validated and compiled once when it is built. - An
Expanderruns expansions and keeps the hygiene record: everyContextit mints, and theOriginthat says which expansion minted it. - A
Budgetbounds what an expander may do — nesting depth, number of expansions, tokens written — so no macro can hang the compiler or exhaust memory. It is on by default.
How an expansion treats each kind of token:
| Token in the output | Where it came from | Its context |
|---|---|---|
| Literal | Written by the template. | A context minted for this expansion. |
| Substituted | Captured from the invocation by a metavariable. | Unchanged — it belongs to the caller. |
| Separator | Written between template repetitions. | The expansion's minted context, marked from the separator's definition context (root for Template::Repeat, ctx for Template::RepeatSeparated). |
Installation
[]
= "1"
= "1" # Token, Span
= "1" # Symbol, Interner
Or from the terminal:
MSRV: Rust 1.85 (Rust 2024 edition).
Quick start
A list! macro that turns a, b, c into [a; b; c]. Tokens here are plain chars to keep the example short; a real language uses its own token-kind enum.
use Interner;
use ;
use ;
let mut names = new;
let e = names.intern;
let s = new; // spans inside the macro definition
// list!( $($e:tt),* ) => [ $($e);* ]
let list = new?;
// The invocation's arguments, as token trees.
let input: = "a,b,c"
.char_indices
.map
.collect;
let mut expander = new;
let out = expander.expand?;
let Some = out.first else ;
let text: String = trees
.iter
.filter_map
.collect;
assert_eq!;
# Ok::
Hygiene
The template below introduces a temporary t; the caller passes in a t of its own. After expansion both are spelled t, but they carry different contexts, so a resolver keyed on (name, context) sees two distinct variables.
use Interner;
use ;
use Span;
let mut names = new;
let x = names.intern;
let with_tmp = names.intern;
// with_tmp!($x:tt) => t = $x
let mac = new?;
let mut expander = new;
let out = expander.expand?;
let contexts: = out
.iter
.filter_map
.collect;
let = ;
assert_ne!;
assert!;
// The expander can say where the macro's `t` came from.
let origin = expander.origin.ok_or?;
assert_eq!;
assert_eq!;
# Ok::
Bounded expansion
Every expander carries a Budget, applied automatically:
| Limit | Default | Stops | Error |
|---|---|---|---|
max_depth |
128 | A macro that calls itself without a base case. | ExpandError::RecursionLimit |
max_expansions |
220 | A macro that fans out into exponentially many calls. | ExpandError::Budget(Limit::Expansions { .. }) |
max_tokens |
222 | A macro whose output grows every round, such as one that doubles its argument. | ExpandError::Budget(Limit::Tokens { .. }) |
Expansion and token counts accumulate in the expander's Usage (Expander::usage). Tokens are charged before they are written, so an oversized expansion is refused without being built. Tighten or loosen the limits with Expander::with_budget / set_budget:
use Interner;
use ;
use Span;
let mut names = new;
let s = new;
// three!() => a b c
let three = new?;
let mut expander = with_budget;
assert!;
assert_eq!;
# Ok::
Long-lived hosts reset per unit of work. A batch compiler uses one expander per compilation and never resets. A language server, REPL, or watch-mode compiler that keeps one expander calls expander.reset_usage() before each document parse, REPL entry, or rebuild, so the budget bounds each unit of work instead of the process, and one hostile document cannot use up the budget of the next. Contexts and origins survive the reset. See examples/budget.rs.
use Interner;
use ;
use Span;
let mut names = new;
let s = new;
let one = new?;
let mut expander = with_budget;
for _document in 0..1_000
assert_eq!; // 1 000 expansions, never over budget
# Ok::
A driver that knows how deep each invocation sits should call Expander::expand_at with that depth: the recursion limit then holds even for a macro that rebuilds its own invocation entirely from captured tokens, such as m!($a:tt $b:tt) => $a $b ($a $b) invoked as m!(m !), which hygiene alone cannot tell apart from the original call. With plain expand, the budget stops that macro instead.
Examples
Four runnable examples ship in examples/. They share a miniature front end in examples/common: a lexer, a tree builder, a parser that lowers macro_rules!-style text such as ($a:ident, $b:ident) => { ... } into patterns and templates, and an expansion driver. That module is the template for wiring macro-lang into a real language.
- Hygiene — the classic
swap!macro, invoked on a variable that shares its temporary's name. The output prints contexts (tmp#2versus the caller'stmp), showing that the swap stays correct. - Vec literal — a three-rule
vec!that picks a rule by shape ((),(x; n),(a, b, c)), expands a separated repetition, and renders a caret diagnostic from a failed match's span. - Recursion — a recursive
count!macro expanded to a fixed point, a runaway macro stopped by the recursion limit, and an expansion backtrace built by following each context's origin outward. - Budget — three hostile macros stopped with no configuration: a self-rebuilding
quine!under a depth-tracking driver (recursion limit) and under a rescanning driver (budget), and a doublingdup!(token budget); then a tight custom budget that still lets ordinary macros through, and a language-server loop that resets usage per document so a hostile document does not starve the next one.
Performance
Patterns are compiled once, when the macro is built, into a nondeterministic automaton; matching simulates it in a single left-to-right pass over the input, merging parses that reach the same point. There is no backtracking, so cost grows linearly with input length even for adversarial patterns. Rules that must start with a fixed token are rejected on the first input entry without running the automaton. The expander keeps every working buffer between calls, so steady-state expansion allocates only the output trees.
Measured with the benchmarks in benches/ (x86_64, Rust stable, release profile, one reused expander):
| Benchmark | What it measures | Windows | Linux (WSL2) |
|---|---|---|---|
list/8 |
$($e:tt),* => [$($e);*] over 8 elements. |
~0.56 µs | ~0.53 µs |
list/512 |
The same over 512 elements (≈ 50 ns per element). | ~27 µs | ~26 µs |
nested/64 |
$( ( $($x:tt)* ) )* over 64 groups of four tokens. |
~16 µs | ~13 µs |
dispatch/rules=16 |
Sixteen rules keyed by a leading token, invoking the last. | ~0.13 µs | ~0.09 µs |
hygiene/literals=64 |
A template writing 64 literal tokens, each marked. | ~0.56 µs | ~0.31 µs |
identity/depth=64 |
$($t:tt)* capturing a 64-deep nested group. |
~4.7 µs | ~3.2 µs |
budget/dup/65536 |
A doubling macro driven until a 216-token budget stops it. | ~2.7 ms | not measured |
budget/quine/16384 |
A self-rebuilding macro under expand, stopped by a 214-expansion budget. |
~2.7 ms | not measured |
budget/limit=128 |
The same macro under expand_at, stopped by the default recursion limit. |
~23 µs | not measured |
The rows above the budget rows were measured at 1.0.0. Budget accounting in 1.1.0 showed no measurable cost on the hot path: a min-of-60-batches A/B against 1.0.0 on Windows put list/512 and nested/64 within 2% of 1.0.0 (criterion runs on the shared build machine drifted by up to 8% between two runs of the same 1.0.0 binary, too noisy to resolve a few percent). The budget benchmarks scale linearly with the budget: budget/dup and budget/quine each take about 4× as long for a 4× larger budget.
Run them yourself:
Criterion writes per-benchmark reports to target/criterion/. Numbers vary by CPU; use the trend across runs, not a single absolute.
Design notes
- Token trees, not syntax trees. Expansion runs before parsing. Grouping by delimiters is the one structure every language agrees on at that point, and it is exactly what a pattern needs: a group matches as a unit, and a metavariable can capture a whole bracketed expression without knowing the grammar inside.
- Hygiene by marking, not renaming. No identifier is rewritten. Each expansion mints a context for the tokens its template introduces, and
Expander::originrecords where every context came from — the definition-site context to fall back on for free names, the macro, and the call site for diagnostics. - Errors at definition time when possible.
Macro::newrejects duplicate bindings, unbound or under-repeated metavariables, repetitions that could match nothing, and template repetitions with nothing to repeat over. A macro that builds can only fail on input-dependent conditions. - Ambiguity is an error. When a rule could match an invocation in two different ways, expansion reports
ExpandError::Ambiguousrather than guessing. Unlike rustc, the matcher still accepts patterns such as$($t:tt)* ;whose apparent ambiguity is resolved by the input that follows. - Deep input is safe. Flattening, matching, transcription, and rebuilding captured groups all run on explicit buffers rather than recursion, so a deeply nested invocation cannot overflow the stack inside the expander.
- Runaway expansion is bounded. An invocation's depth is the deepest of the expansions that produced its name token or any input token (and, through
expand_at, the depth the driver tracked), so a macro that expands into itself without a base case stops withExpandError::RecursionLimit(128 nested expansions by default). A defaultBudgetcaps total expansions and tokens, which stops doubling and fan-out bombs that never nest deeply.
Testing
The suite runs on Windows, Linux (WSL2 Ubuntu), and macOS through the CI matrix, on stable and the 1.85 MSRV:
The property tests in tests/proptests.rs hold the matcher to an independent oracle: for arbitrary patterns and inputs, a brute-force counter of every distinct parse must agree with the expander. No parse means NoMatch, exactly one means success, and more than one means Ambiguous. On every unique match, a template that mirrors the pattern must reproduce the input token for token. Every rust example in this README and in docs/API.md is compiled and run as a doctest, so the published examples cannot drift from the API.
Cross-platform support
- Linux (x86_64, aarch64)
- macOS (x86_64, Apple Silicon)
- Windows (x86_64)
The expander uses no operating-system facilities and no platform-specific code; behaviour is identical on every target.
Contributing
See REPS.md for the engineering standards every change is held to, and dev/ROADMAP.md for the plan to 1.0. Before a PR: cargo fmt --all, cargo clippy --all-targets --all-features -- -D warnings, and cargo test --all-features must be clean.