🎓 A1Learner
🔍

Rust Push-Down Accumulation

Push-down accumulation is a pattern where a recursive macro carries its finished tokens inside its own next call. The last call emits the accumulator as one complete construct.

The tempting way can never work

Each step here hands back an unfinished list — a comma and a value, with no brackets. Rust forbids it: an expansion must be a complete construct:

// Forbidden shape: the middle step is not a complete piece of code.
(2, $e:expr) => { $e, accum!(1, $e) };

Carry the finished part along instead

This step reads one new token and calls itself with the token pushed onto the front of the accumulator:

(@step [$($acc:tt)*] $head:tt $($tail:tt)*) => {
    reversed!(@step [$head, $($acc)*] $($tail)*)
};

The last step emits everything at once

When no input tokens remain, the accumulator is finally written out as one complete construct:

(@step [$($acc:tt)*]) => { vec![$($acc)*] };

Example

macro_rules! reversed {
    (@step [$($acc:tt)*]) => { vec![$($acc)*] };
    (@step [$($acc:tt)*] $head:tt $($tail:tt)*) => {
        reversed!(@step [$head, $($acc)*] $($tail)*)
    };
    ($($input:tt)*) => { reversed!(@step [] $($input)*) };
}
fn main() {
    let nums = reversed!(1 2 3 4);
    println!("reversed = {:?}", nums);
}

Key points

  • Push-down accumulation: a recursive macro passes a growing bundle of tokens — the accumulator — down into its own next call
  • It exists because every macro expansion must be a complete construct
  • Half an expression or half a list can never be handed back
  • The rule holds even between two macros
  • The accumulator is kept as raw tokens, $($acc:tt)*, so nothing tries to parse the half-built result
  • A final arm, matched when the input runs out, emits the accumulator as the real code at last
  • The pattern is usually combined with internal rules: the @ arms do the stepping, the plain arm just starts the process
  • Accumulators cost time like munchers do: every step re-matches the whole bundle, so keep accumulated results small

In this example, the plain arm starts the work. It calls the macro again with an empty accumulator, [] , and the input 1 2 3 4. The stepping arm reads the first token, 1, and pushes it onto the accumulator, giving [1,]. The next steps push 2, then 3, then 4 in front, so the accumulator becomes [4, 3, 2, 1,]. When no input is left, the first arm matches and writes the accumulator out as one complete vec!. Nothing half-built ever left the macro — the finished list travelled inside the calls until it was whole.

Note

Writers often draw these macros as (input) -> (output) with an arrow between the work and the accumulator

The arrow is only a reading aid — in real code both sides are ordinary token groups

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

Why do macros build results with push-down accumulation at all?