Step 4 of 6

Recursive macros

A macro can call itself in its expansion. Each call peels off part of the input until a base rule matches, just like a recursive function. This is how you handle input that repetition alone can't, such as combining values pairwise.

macro_rules! count {
    () => { 0usize };
    ($head:expr $(, $tail:expr)*) => { 1usize + count!($($tail),*) };
}

fn main() {
    println!("{}", count!());
    println!("{}", count!(7));
    println!("{}", count!("a", "b", "c"));
}

0
1
3

Expanding count!("a", "b", "c") by hand:

count!("a", "b", "c")
1usize + count!("b", "c")
1usize + 1usize + count!("c")
1usize + 1usize + 1usize + count!()
1usize + 1usize + 1usize + 0usize

All of this happens at compile time; the program just contains the sum (which the optimizer folds to 3). Two rules matter, like in any recursion: a base case (()) and a step that makes the input smaller.

Accumulators and internal rules

Recursing "first value, then the rest" builds the result from the right. For subtraction that's the wrong grouping. The fix is an accumulator: carry the result so far through the recursive calls. Rules that start with a marker like @acc are internal rules, a naming convention for helper rules that callers aren't meant to use.

// Right to left: 100 - (20 - 5)
macro_rules! sub_right {
    ($x:expr) => { $x };
    ($x:expr, $($rest:expr),+) => { $x - sub_right!($($rest),+) };
}

// Left to right with an accumulator: (100 - 20) - 5
macro_rules! sub_left {
    (@acc $acc:expr) => { $acc };
    (@acc $acc:expr, $x:expr $(, $rest:expr)*) => { sub_left!(@acc ($acc - $x) $(, $rest)*) };
    ($first:expr $(, $rest:expr)*) => { sub_left!(@acc $first $(, $rest)*) };
}

fn main() {
    println!("{}", sub_right!(100, 20, 5));
    println!("{}", sub_left!(100, 20, 5));
}

85
75

The public rule (last) starts the accumulator with the first value. Each @acc step folds in one more value, ($acc - $x), until none are left. Macros that eat their input a few tokens at a time like this are called TT munchers (they often match $($rest:tt)*), and they're how people build small languages inside macros.

Common mistakes

• Forgetting the base case, or a step that doesn't shrink the input: the expansion never ends, and you get error: recursion limit reached while expanding `count!` . The limit is 128 levels by default; #![recursion_limit = "256"] raises it, but if you need that, a different design is usually better.
• Expanding an argument in several recursive branches, which evaluates it several times. Bind it to a local first, as in step 1.
• Deep recursion slows compilation. Each level is a full macro expansion. Fine for a handful of values, not for thousands of tokens.

Your task

Write max!, which takes one or more values and evaluates to the largest. max!(x) is x; for more values, compare the first with max! of the rest. Evaluate each argument only once (bind it with let inside a block).

Challenge 2

Write first_some!, which takes one or more Option expressions and evaluates to the first one that is Some, or the last one if all are None. It must be lazy: later arguments are only evaluated if the earlier ones were None (a function can't do that without closures). Typical use: first_some!(from_env(), from_file(), Some(8080)).

Challenge 3

Build a tiny DSL with a TT muncher: calc!(10 minus 2 minus 3) is 5, calc!(2 plus 3 times 4) is 20. The words plus, minus and times work strictly left to right (no precedence), and every number is a literal. Use an accumulator with internal @acc rules:

• calc!(n ...) starts with calc!(@acc n; ...)
• calc!(@acc acc; plus x ...) continues with calc!(@acc (acc + x); ...) (same for minus and times)
• calc!(@acc acc;) with nothing left is the answer

Previous: Repetition Next: Hygiene, small DSLs and debugging macros