Macro recursion and incremental TT munchers

A macro that eats its input one token at a time — the mechanism behind every mini-DSL in the ecosystem.

pub fn evaluate() -> Vec<i64>

Two macros to build. count_tokens! counts token trees. rpn! evaluates reverse-Polish notation at compile time:

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

Look at that last one before moving on: (c d) counts as one. A tt is one token tree — either a single token, or an entire delimited group with everything inside it. That is why tt munchers can walk over arbitrarily nested syntax without getting lost.

The muncher pattern

Three lines describe every token-tree muncher ever written:

1. A rule that matches the empty input and terminates.
2. A rule that matches one leading token tree, does something with it, and recurses on the rest.
3. Base case first.

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

`$head:tt $($rest:tt)*` is the shape to internalise: peel one, keep the tail.

"Base case first" is habit rather than necessity here — the recursive rule
demands at least one token, so it cannot swallow the empty case. But the moment
a rule matches *everything*, order becomes load-bearing, which is exactly what
the starter demonstrates.

## Push-down accumulation

`rpn!` cannot work by peeling alone, because it needs a stack. A macro cannot
return a value to itself mid-recursion — there is no "return" — so the only place
to keep state is **in the arguments of the next invocation**.

The state travels in a bracketed group:

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

and every rule rewrites the stack and hands it on:

- a literal → push it: `[$lit $(, $stack)*]`
- `+` → pop two, push their sum: `[$a + $b $(, $rest)*]`
- nothing left, one item on the stack → that item is the answer

The `[...]` matters. Wrapping the accumulator in a delimiter keeps it a **single
token tree**, so `$($stack:expr),*` inside the brackets can be re-matched cleanly
and the parser never confuses stack contents with input tokens. Drop the brackets
and you get local-ambiguity errors that read like nonsense.

`@run` is a tag that marks an internal rule — a convention with no special
meaning, covered properly in item 18.9. It is here because the public entry rule
`($($t:tt)+)` matches *everything*, including the macro's own recursive calls,
and the tag is what keeps them apart.

## The trace worth doing by hand

`rpn!(2 3 + 4 *)`:

```text
@run []            2 3 + 4 *
@run [2]           3 + 4 *
@run [3, 2]        + 4 *
@run [2 + 3]       4 *          <- '+' popped two, pushed one
@run [4, 2 + 3]    *
@run [(2 + 3) * 4]              <- '*' popped two, pushed one
(2 + 3) * 4  ==  20
```

Notice what happened at the last step. The stack held `2 + 3` as an `expr`
fragment, and when the `*` rule wrote `$a * $b`, that fragment went in
**atomically** — item 18.4's lesson, now doing load-bearing work. If the stack
had held raw `tt`s, the expansion would have been `2 + 3 * 4` and the answer
would have been 14.

## The cost, and the wall

Munchers are **O(n²) in compile time**. At each step the matcher re-scans the
entire remaining token stream to bind `$($rest:tt)*`, so an *n*-token input does
roughly *n²/2* token comparisons. For the sizes here that is invisible; for a
macro invoked with a few hundred tokens it is measurable, and it is why large
`macro_rules!` DSLs have a reputation for slow builds.

There is a hard wall too. The default `recursion_limit` is **128**, and a
one-token-per-step muncher exhausts it at about 125 tokens. Raising it means
putting

```rust
#![recursion_limit = "512"]
```

at the very top of the crate — it is a crate-level inner attribute and must come
before any item. Every input in this problem is comfortably under 20 tokens, so
you will not need it, but knowing the number is what stops you from staring at
"recursion limit reached while expanding" wondering what you did wrong.

::: question What actually goes wrong if the public entry rule is listed first?

It matches its own recursive call, forever.

The entry rule is `($($t:tt)+)` — one or more token trees, which describes every
non-empty invocation. Put it above the `@run` rules and `rpn!(@run [] 3 4 +)`
matches it, expanding to `rpn!(@run [] @run [] 3 4 +)`, which matches it again,
which expands to… The compiler stops at the recursion limit and tells you so.

This is the concrete reason for "base case first, catch-alls last", and the
concrete reason internal rules get a sigil. The starter has the entry rule in the
wrong place so you can read the error once and never write it again.
:::

## Your job

Give `count_tokens!` its terminating rule, and move `rpn!`'s public entry rule to
where it belongs.