tlborm Documentation

A TT Muncher is a recursive macro_rules! macro used to parse complex grammars. It works by incrementally processing input one step at a time:

1. Match: It identifies a specific sequence of tokens at the start of the input.
2. Munch: It removes (consumes) those tokens.
3. Recurse: It calls itself recursively on the remaining input, which is captured as a $($tail:tt)* repetition.

The use of the tt (token tree) fragment specifier is critical because it is the only way to losslessly capture the unprocessed part of the input for the next recursive step.

Restrictions

• You can only match against literals and grammar constructs supported by macro_rules!.
• You cannot match unbalanced groups.
• You must be mindful of the macro recursion limit, as macro_rules! does not perform tail recursion optimization.

macro_rules! mixed_rules {
    () => {};
    (trace $name:ident; $($tail:tt)*) => {
        {
            println!(concat!(stringify!($name), " = {:?}"), $name);
            mixed_rules!($($tail)*);
        }
    };
    (trace $name:ident = $init:expr; $($tail:tt)*) => {
        {
            let $name = $init;
            println!(concat!(stringify!($name), " = {:?}"), $name);
            mixed_rules!($($tail)*);
        }
    };
}

fn main() {
    let a = 42;
    let b = "Ho-dee-oh-di-oh-di-oh!";
    let c = (false, 2, 'c');
    mixed_rules!(
        trace a;
        trace b;
        trace c;
        trace b = "They took her where they put the crazies.";
        trace b;
    );
}

When working with Rust source analysis (particularly when writing macros), you must distinguish between Token Trees and the Abstract Syntax Tree (AST).

Token Trees

Token trees represent the hierarchical grouping of tokens using delimiters.

• Leaves: Almost all individual tokens are leaves in a token tree.
• Interior Nodes: The grouping tokens (...), [...], and {...} act as interior nodes that provide structure.
• Structure: A token tree is purely lexical. For example, the expression a + b + (c + d[0]) + e results in seven distinct token trees at the root level, rather than a single tree.
• Constraints: It is impossible to have unpaired delimiters or incorrectly nested groups within a token tree.

Abstract Syntax Tree (AST)

Parsing converts the token stream into an AST, which represents the actual syntactic and logical structure of the program.

• Purpose: The AST builds the semantic relationships (e.g., identifying a BinOp with a lhs and rhs).
• Limitation: At the AST stage, the compiler knows the structure but does not yet know the identity or origin of variables (e.g., it knows a variable is named a, but not what a refers to).

Comparison Example

For the expression a + b + (c + d[0]) + e:

• Token Trees see the grouping: «a» «+» «b» «+» «( ... )» «+» «e».
• AST sees the mathematical operations: A nested tree of BinOp nodes representing the order of operations.

Because of macro hygiene, a macro exported from one crate cannot reliably access other items (functions, modules, etc.) in that same crate using relative paths. The items in the calling crate will have a different syntax context.

To solve this, use the $crate metavariable. $crate expands to the absolute path of the crate where the macro was originally defined.

Requirements:

• When using $crate to refer to non-macro items (like functions or modules), you must use a fully qualified module path (e.g., $crate::module::item).

//// Definitions in the `helper_macro` crate.
#[macro_export]
macro_rules! helped {
    // Use $crate to ensure 'helper' is found regardless of where 'helped!' is called
    () => { $crate::helper!() }
}

#[macro_export]
macro_rules! helper {
    () => { () }
}

//// Usage in another crate.
use helper_macro::helped;

fn unit() {
   // Works because $crate expands to `helper_macro`
   helped!();
}

The Repetition Replacement pattern is used when you want to discard a matched repetition sequence and instead use its length to drive a repeated pattern. This is useful when the specific values of the matched items are irrelevant, but the number of items determines how many times an expression should be repeated.

To implement this, you define a helper macro (often called replace_expr) that accepts the repetition sequence and a replacement expression, but only returns the replacement expression. This allows you to use the repetition syntax $( ... )* to repeat the replacement expression exactly as many times as there were items in the original sequence.

macro_rules! replace_expr {
    ($_t:tt $sub:expr) => {$sub};
}

macro_rules! tuple_default {
    ($($tup_tys:ty),*) => {
        (
            $( 
                replace_expr!(($tup_tys) Default::default()),
            )*
        )
    };
}

assert_eq!(tuple_default!(i32, bool, String), (i32::default(), bool::default(), String::default()));

A traditional approach is to use recursive macro calls.

Performance Note: To avoid performance issues with integer type inference in older rustc versions, use explicitly typed literals like 0usize or use the as keyword (e.g., 0 as $ty).

Limitations: Simple recursion (matching one token at a time) will easily hit the compiler's recursion limit. To handle larger inputs (up to ~1,200 tokens), you can match multiple tokens at once in each recursive step to reduce the depth of the recursion tree.

// Simple recursion (limited depth)
macro_rules! count_tts {
    () => {0usize};
    ($_head:tt $($tail:tt)*) => {1usize + count_tts!($($tail)*)};
}

// Optimized recursion (matches multiple tokens to increase capacity)
macro_rules! count_tts {
    ($_a:tt $_b:tt $_c:tt $_d:tt $_e:tt
     $_f:tt $_g:tt $_h:tt $_i:tt $_j:tt
     $_k:tt $_l:tt $_m:tt $_n:tt $_o:tt
     $_p:tt $_q:tt $_r:tt $_s:tt $_t:tt
     $($tail:tt)*)
        => {20usize + count_tts!($($tail)*)};
    ($_a:tt $_b:tt $_c:tt $_d:tt $_e:tt
     $_f:tt $_g:tt $_h:tt $_i:tt $_j:tt
     $($tail:tt)*)
        => {10usize + count_tts!($($tail)*)};
    ($_a:tt $_b:tt $_c:tt $_d:tt $_e:tt
     $($tail:tt)*)
        => {5usize + count_tts!($($tail)*)};
    ($_a:tt
     $($tail:tt)*)
        => {1usize + count_tts!($($tail)*)};
    () => {0usize};
}

Push-down accumulation is a macro pattern used to incrementally build up a sequence of tokens without requiring each intermediate step to expand into a complete, valid Rust syntax element (like a full expression or item).

In standard Rust macro expansion, every intermediate step must result in a complete syntax element. This makes it impossible to expand a macro into a partial construct (e.g., an incomplete array literal). Push-down accumulation bypasses this by using a recursive pattern where each layer adds to an accumulator of tokens ($($body:tt)*) and passes it to the next layer. The final layer in the recursion then emits the complete, valid construct.

This pattern is a core component of incremental TT munchers and allows for the construction of arbitrarily complex intermediate results.

macro_rules! init_array {
    [$e:expr; $n:tt] => { 
        {   
            let e = $e; 
            accum!([$n, e.clone()] -> [])
        }
    };
}

macro_rules! accum {
    ([3, $e:expr] -> [$($body:tt)*]) => { accum!([2, $e] -> [$($body)* $e,]) };
    ([2, $e:expr] -> [$($body:tt)*]) => { accum!([1, $e] -> [$($body)* $e,]) };
    ([1, $e:expr] -> [$($body:tt)*]) => { accum!([0, $e] -> [$($body)* $e,]) };
    ([0, $_:expr] -> [$($body:tt)*]) => { [$($body)*] };
}

let strings: [String; 3] = init_array![String::from("hi!"); 3];
assert_eq!(format!("{:?}", strings), "[\"hi!\", \"hi!\", \"hi!\"]");

A macro_rules! macro uses pattern matching to parse input tokens. You define rules that match specific token sequences and capture parts of the input into metavariables.

Common Matcher Types

• $name:expr: Captures a valid expression.
• $name:ty: Captures a type.
• $name:item: Captures an item (like a function or struct).

Repetition Syntax

You can match repeating sequences using the $( ... ) syntax:

• $( ... ),+: Matches one or more repetitions, separated by a comma.
• $( ... ),*: Matches zero or more repetitions.
• $( ... )?: Matches zero or one repetition (optional).

Example Rule Construction

To match the syntax a[n]: $sty = $($inits),+ , ... , $recur, the rule would look like:

macro_rules! recurrence {
    ( a[n]: $sty:ty = $($inits:expr),+ , ... , $recur:expr ) => { /* expansion */ };
}

In this example:

• a[n]: is a literal token sequence.
• $sty:ty captures a type into the metavariable sty.
• $inits:expr captures one or more expressions separated by commas.
• , ... , is a literal token sequence.
• $recur:expr captures the final recurrence expression.