macro-lang 1.0.0

Hygienic macro expansion: pattern match + template substitution.
Documentation

The model

A handful of plain-data types and one engine:

  • A Tree is a token tree: a single token, or a delimited group of trees. Invocations go in as trees and expansions come out as trees.
  • A Rule pairs a Pattern (what an invocation must look like) with a Template (what it expands to). Patterns bind metavariables — $x:tt — and repeat — $( ... ),*; templates substitute and repeat them.
  • A Macro is a name and an ordered list of rules, validated and compiled once when it is built.
  • An Expander runs expansions and keeps the hygiene record: every Context it mints, and the Origin that says which expansion minted it.

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.

Installation

[dependencies]
macro-lang = "1"
token-lang = "1"    # Token, Span
intern-lang = "1"   # Symbol, Interner

Or from the terminal:

cargo add macro-lang token-lang intern-lang

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 intern_lang::Interner;
use macro_lang::{Context, Expander, Fragment, Kleene, Macro, Pattern, Rule, Template, Tree};
use token_lang::{Span, Token};

let mut names = Interner::new();
let e = names.intern("e");
let s = Span::new(0, 0); // spans inside the macro definition

// list!( $($e:tt),* ) => [ $($e);* ]
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)),
        }],
    }],
}])?;

// The invocation's arguments, as token trees.
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 text: String = trees
    .iter()
    .filter_map(|t| match t {
        Tree::Token { token, .. } => Some(token.kind),
        Tree::Group { .. } => None,
    })
    .collect();
assert_eq!(text, "a;b;c");
# Ok::<(), Box<dyn std::error::Error>>(())

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 intern_lang::Interner;
use macro_lang::{Context, Expander, Fragment, Macro, Pattern, Rule, Template, Tree};
use token_lang::Span;

let mut names = Interner::new();
let x = names.intern("x");
let with_tmp = names.intern("with_tmp");

// with_tmp!($x:tt) => t = $x
let mac = Macro::new(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),
    ],
}])?;

let mut expander = Expander::new();
let out = expander.expand(&mac, &[Tree::token('t', Span::new(9, 10))], 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();
let (macro_t, caller_t) = (contexts[0], contexts[1]);
assert_ne!(macro_t, caller_t);
assert!(caller_t.is_root());

// The expander can say where the macro's `t` came from.
let origin = expander.origin(macro_t).ok_or("not minted here")?;
assert_eq!(origin.macro_name, with_tmp);
assert_eq!(origin.call_site, Span::new(0, 11));
# Ok::<(), Box<dyn std::error::Error>>(())

Examples

Three 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#2 versus the caller's tmp), showing that the swap stays correct.
    cargo run --example hygiene
    
  • 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.
    cargo run --example vec_literal
    
  • 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.
    cargo run --example recursion
    

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

Run them yourself:

cargo bench --bench bench

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::origin records 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::new rejects 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::Ambiguous rather 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 recursion is bounded. An invocation's depth is read from the context of its name token, so a macro that expands into itself without a base case stops with ExpandError::RecursionLimit (128 nested expansions by default).

Testing

The suite runs on Windows, Linux (WSL2 Ubuntu), and macOS through the CI matrix, on stable and the 1.85 MSRV:

cargo test                       # unit + integration + property + doctests
cargo clippy --all-targets --all-features -- -D warnings
cargo bench --bench bench

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.