Expansion Depth Limits and Token Opacity

A macro that needs to process a list of unknown length cannot use a loop, because the macro language has no loop. It uses recursion: match the first element, handle it, and re-invoke itself on the remainder. The pattern works, and it has two costs that are invisible until the input grows — the expansion depth grows with the length of the list, and the fragments already captured cannot be taken apart again.

Recursion by re-invocation

The pattern is called a tt-muncher: the macro consumes one token tree at a time and passes the rest to itself.

macro_rules! count_idents {
    () => { 0usize };
    ($first:ident $($rest:ident)*) => {
        1usize + count_idents!($($rest)*)
    };
}

const N: usize = count_idents!(a b c d e);

Each invocation strips one identifier and emits an addition whose right operand is a new invocation on the remainder. The base case is the empty invocation, which matches the first rule. Expansion stops when the remainder is empty, and the resulting expression is a sum of literals that the optimizer folds.

The recursive call is not expanded while the outer invocation’s replacement is being built. It is emitted as tokens and expanded afterwards. That ordering is what makes the pattern work at all, and it is also what makes the cost linear: the invocation emitted by one expansion is a child of that expansion, so its own children are grandchildren, and a list of n elements produces a chain of n nested expansions even though they are performed one after another.

Why a C macro cannot do this

The contrast with the preprocessor is instructive because the preprocessor forbids exactly the pattern the muncher depends on.

#define COUNT(...) COUNT(__VA_ARGS__)

A macro name encountered while its own replacement list is being rescanned is not expanded again. The standard enforces this by marking each token with the set of macro names that are ineligible for further expansion, so a second expansion of the same name on the same tokens never happens and the name survives into the output as ordinary tokens. The rule makes C expansion total: whatever the definitions say, the preprocessor stops. It also makes the muncher impossible, because every recursive invocation would be suppressed by the same rule.

Rust does not suppress the recursive invocation, and the reason is that the invocation is not encountered during the rescan of the same expansion. It appears in the output of an expansion that has already completed, and the expander processes it as a new, separate item of work. A macro can therefore invoke itself as long as the invocation appears in a replacement that was produced by a different, finished expansion — which is true of every muncher step, since each step matched a strictly smaller input and the replacement is built by transcription rather than by rescanning the matcher’s own name.

The distinguishing property is not self-reference but the size of the input. A macro whose rules make no progress — every rule matching the same tokens and transcribing a fresh invocation of the same macro on those tokens — produces an expansion whose child is an expansion of the same macro on the same tokens. The expander does not detect this as a loop; it simply keeps expanding until the depth limit stops it. That is why the limit exists.

The limit, and how it is counted

Rust’s recursion_limit attribute, applied at crate level, sets the maximum depth for potentially infinitely-recursive compile-time operations, of which macro expansion is one; the default in rustc is 128. A muncher that raises the depth by one per element therefore fails once the list is longer than the budget the surrounding expansion path has already consumed, and the diagnostic is an error naming the macro and mentioning the recursion limit rather than an error about the input. The limit is a compiler resource guard rather than a language rule, and the attribute raises it for the whole crate.

One detail matters when counting. An invocation that appears inside a nested token group, and every invocation inside the expansion that produced it, contributes to the same nesting, so the depth a muncher consumes per element also depends on how deeply the invocation sits in the surrounding expression. A muncher used inside a vec![] grows the same chain as one used at statement level; the depth is the sum along the path, not a count of self-invocations.

Three consequences follow from the limit being counted in expansion depth.

The first is that the limit bounds list length, not total expansion work. A macro that processes a long list by recursing one element at a time needs one level per element; a macro that processes eight elements per step needs one level per eight. Chunking the recursion is the standard remedy, and it trades pattern complexity for depth: each rule matches a fixed number of elements and the last rule handles the remainder, so the depth is the length divided by the chunk size.

The second is that the limit is per invocation tree, not per crate. Two independent munchers over 100 elements each do not add their depths together, because neither is nested inside the other. Only a macro whose expansion contains another macro’s invocation accumulates.

The third is that the diagnostic arrives at the deepest point. When the limit is hit, the compiler reports the macro that was being expanded when the count ran out, which for a muncher is the same macro at every level. The message therefore identifies the pattern rather than the input, and the input’s length has to be inferred from the source. This is why the failure is often described as “the macro stopped working when the list got long” rather than as a recursion error.

A procedural macro has no equivalent limit, because its recursion is the host language’s function calls rather than the expander’s nested expansions. It can walk a token stream of any length, bounded by the stack, and it pays for that with the isolation described in procedural macros over token streams. The trade is a real one: the muncher’s limit is what makes its cost predictable, and the procedural macro’s absence of a limit is what makes a pathological input a stack overflow instead of a diagnostic.

Opacity: the fragments that cannot be matched again

The second rule is the one that surprises people. When a macro forwards a captured fragment to another macro, the second macro’s matchers see an opaque abstract syntax node rather than the fragment’s tokens: a later pattern cannot match individual tokens inside it, and only a fragment specifier of the same type — or a literal token, for the ident, lifetime, and tt kinds — can take its place. The representation records that the tokens were parsed and classified at capture time.

The purpose is to prevent an argument from being reinterpreted after it has been classified. If $x:expr were transparent, a macro invoked with 1 + 2 could have its argument split by a subsequent pattern expecting two token trees around a +, which would change the meaning of an argument that had already been accepted as a single expression.

The consequence is that a macro cannot destructure a fragment that arrived through a typed fragment specifier. $x:expr cannot be taken apart into its operator and operands, because the whole fragment is one opaque unit. To destructure, the macro must capture the input as $($t:tt)* — raw token trees — and do its own matching over them.

macro_rules! sum_all {
    // entry: hand the whole input to the accumulator-passing rules
    ($($t:tt)*) => { sum_all!(@parse [] $($t)*) };
    // base case: nothing left to consume
    (@parse [$($acc:tt)*]) => { 0 $(+ $acc)* };
    // move one token from the input to the accumulator, then recurse
    (@parse [$($acc:tt)*] $next:tt $($rest:tt)*) => {
        sum_all!(@parse [$($acc)* $next] $($rest)*)
    };
}

The accumulator is bracketed so that a rule can tell it apart from the remaining input. It is built from tt rather than from expr for the reason above: an expr captured in one step arrives at the next as an opaque unit, and the rule that adds one more token to it would be unable to look inside. A tt accumulator keeps the tokens individually matchable, at the cost of deferring all validation to the base case, where the assembled expression is finally parsed. The entry rule has to hand the whole input over in one step, because a rule that tried to accumulate expr fragments would be re-parsing at every step and would refuse anything that is not yet a complete expression.

The same opacity explains why a macro that captures $e:expr cannot test whether $e is a literal. The literal-ness was decided at capture, and the fragment is now opaque. The workaround is to capture as tt from the start and match the literal at the outer level, which pushes the classification into the macro’s own patterns.

When opacity is the point

The opacity rule is not only a restriction; it is what makes fragment classification stable. Because a captured fragment cannot be re-split, a macro author can rely on $e:expr meaning exactly one expression for the rest of the expansion, regardless of what the expression contains. A system without opacity would let an inner macro reinterpret an argument, which is the same class of problem as identifier capture, applied to structure rather than to names.

The parallel is close enough to be worth stating: hygiene protects identifiers from being rebound by a context they were not written in, and opacity protects token groups from being re-parsed by a pattern they were not written for. Both work by attaching provenance to substituted material, and both cost the macro author the ability to inspect what was substituted. The syntax object representation is the same idea with scope sets on identifiers; the opaque fragment is its token-level counterpart.

What the three rules jointly exclude

Re-invocation, a depth limit, and opacity define the boundary of a pattern-matching macro system. It can process a flat list up to the depth limit, and past that only by chunking. It cannot inspect the interior of a classified fragment, so any macro that needs to rewrite an expression’s structure must capture tokens and reimplement the classification. And it cannot express a loop whose trip count is known only at expansion time, because there is no loop — only a recursion whose depth is the trip count.

The last of those is the one that produces the most surprising failures. A muncher that works on a five-element list works by construction; the same muncher on a five-hundred-element list fails at a depth the author never considered, and the failure is in the compiler’s resource accounting rather than in the macro’s logic. The remedies are all structural: raise the limit, chunk the recursion, or move the work into a procedural macro where the recursion is a function call. Each is a decision about where the depth is paid, and none removes the fact that a pattern-matching expander processes a list by nesting.