Macro recursion and incremental TT munchers

A macro_rules! macro can process its input one piece at a time by matching the first piece and calling itself on the rest. This pattern is often called a token-tree muncher, or "TT muncher". You will finish two such macros.

pub fn evaluate() -> Vec<i64>

The exercise contract

count_tokens! expands to the number of token trees (defined below) in its input, as an i64. rpn! takes an arithmetic expression written in reverse Polish notation (RPN), where each operator comes after its two operands, and expands to the ordinary Rust expression that computes it:

rpn!(3 4 +)            // 3 + 4 = 7
rpn!(2 3 4 * +)        // 2 + (3 * 4) = 14
rpn!(2 3 + 4 *)        // (2 + 3) * 4 = 20
count_tokens!(a b (c d) 1 + 2)   // 6

evaluate() is already written. It returns these nine values, in this order:

The tests ask for some of these positions by index, or for the whole list, so leave evaluate() and the order of its calls unchanged. The starter does not compile; the work is in the two macro definitions.

rpn! supports integer literals and the three binary operators +, - and *. - means a - b where b is the value on top of the stack, so rpn!(10 2 -) is 10 - 2. A literal may carry a leading minus sign, as in rpn!(-7), but only while fewer than two values are on the stack: with two or more, the - is read as subtraction first (see the last section).

What a token tree is

A token is one indivisible piece of source text: an identifier such as a, a literal such as 1 or "s", a lifetime such as 'a, or a punctuation symbol. Multi-character symbols such as :: and => are single tokens.

A token tree (the tt fragment in a macro pattern) is either one token that is not a bracket, or a whole delimited group: an opening (, [ or {, everything inside it, and the matching closing bracket. That is why (c d) counts as one in the example above, and why the six trees there are a, b, (c d), 1, + and 2. Because a group is always one tree, a muncher that steps over tts never splits a bracketed group in the middle.

Peeling one token tree at a time

A simple muncher has two rules:

1. A rule that matches the empty input and stops.
2. A rule that matches one leading token tree, does something with it, and calls the macro again on the remaining trees.

macro_rules! count_tokens {
    () => { 0i64 };
    ($head:tt $($rest:tt)*) => { 1i64 + count_tokens!($($rest)*) };
}

$head:tt binds the first tree, and $($rest:tt)* binds zero or more trees after it. count_tokens!(a b) therefore expands to 1i64 + count_tokens!(b), then to 1i64 + 1i64 + count_tokens!(), and the empty rule turns the last call into 0i64. Without that empty rule, the final call count_tokens!() matches no rule and the compiler reports "unexpected end of macro invocation".

macro_rules! tries its rules from top to bottom and uses the first one that matches. In count_tokens! the order of the two rules does not matter, because the second rule needs at least one tree and so can never match empty input. Order does matter as soon as one rule is general enough to match what another rule was meant to handle, which is the bug in the starter's rpn!.

Carrying a stack between calls

Evaluating RPN needs a stack: literals are pushed, and each operator pops two values and pushes the result. A macro cannot keep a variable between expansion steps. Each step only rewrites the tokens of one call into new tokens. So rpn! stores its stack in the arguments of the next call:

rpn!(@run [stack contents] remaining tokens...)

The stack is a comma-separated list of expressions with the top first. Each internal rule reads the next input token, rewrites the stack and calls rpn! again:

• a literal: push it, [$lit $(, $stack)*]
• +: take the top value $b and the one below it $a, and push $a + $b, giving [$a + $b $(, $rest)*] (- and * work the same way)
• no input left and exactly one value on the stack: that value is the result

The square brackets mark where the stack ends and the remaining input begins. They are needed because a macro pattern may not follow an expr fragment with just anything. Only =>, , or ; may come after one. A pattern such as @run $($stack:expr),* $lit:literal ... is rejected when the macro is defined, with an error saying that $stack:expr may be followed by $lit:literal, which is not allowed for expr fragments. Inside [...], the list of expressions is followed by the closing bracket, which is allowed.

@run is a marker for the internal rules. @ has no special meaning in macro_rules!; it is used here because no RPN input begins with @, so only the macro's own recursive calls start with it. Internal rules are covered in more depth in item 18.9.

The public entry rule, ($($t:tt)*), accepts any input and starts the evaluation with an empty stack by calling rpn!(@run [] ...). It also matches every @run call, because those calls are token trees too. The marker makes internal calls recognisable, but the entry rule still has to come after all the @run rules so that those rules get the first chance to match.

A trace by hand

rpn!(2 3 + 4 *):

@run []            2 3 + 4 *
@run [2]           3 + 4 *
@run [3, 2]        + 4 *
@run [2 + 3]       4 *          <- '+' popped 3 and 2, pushed 2 + 3
@run [4, 2 + 3]    *
@run [(2 + 3) * 4]              <- '*' popped 4 and 2 + 3, pushed the product
(2 + 3) * 4  ==  20

The parentheses in the last steps are not tokens that the macro writes. They show grouping that comes from the expr fragment. When a pattern captures 2 + 3 as $a:expr, the compiler treats the captured value as one complete expression, and substituting it into $a * $b multiplies the whole sum by 4. If the macro instead pasted the plain tokens 2 + 3 in front of * 4, the result would read 2 + 3 * 4, and normal precedence would give 14. Item 18.4 looks at this difference in detail.

The macro does not run the arithmetic. It expands to an ordinary expression, and that expression is evaluated like any other Rust code. Because the expression uses only literals, it is also accepted where a constant is required, for example const C: i64 = rpn!(2 3 + 4 *);.

Limits and malformed input

Each step of a muncher matches the remaining input again, so the total matching work grows roughly with the square of the input length. For short inputs such as these it is not noticeable.

There is also a limit on how deeply macro calls may nest. The default recursion_limit is 128. With Rust 1.98.1, count_tokens! handles 127 token trees and fails on 128, and this rpn! handles inputs of up to about 125 tokens, because its entry rule uses one extra level. The error reads "recursion limit reached while expanding". The limit can be raised with a crate-level inner attribute, which goes at the top of the crate root before any item:

#![recursion_limit = "512"]

Every input in this problem has fewer than 20 tokens, so you will not need it.

The same error also appears for input that rpn! cannot evaluate, such as rpn!(1 +), rpn!(1 2) or rpn!(). When no @run rule matches, the internal call falls through to the entry rule, which wraps it in another @run [] call that also fails to match, and so on until the limit is reached. The negative-literal restriction above causes the same failure: in rpn!(5 1 -2) the stack holds two values when - arrives, so the subtraction rule fires and computes 5 - 1, leaving 2 and then an unfinished stack of two values.

Your job

Add the rule that ends count_tokens!'s recursion, and move rpn!'s public entry rule below the @run rules.