Macro matching tokens recursive expansion

Question

I'm triying to implement a macro that will expand a brainfuck program (after starting with some simpler code, in which I had problems coming up with a solution already: How to parse single tokens in rust macros). The problem is that at some point of the recursive matching it can never match the end:

error: recursion limit reached while expanding the macro `brainfuck`
   --> src/lib.rs:119:9
    |
119 |         brainfuck!(@impl cell; $($all_tokens)*);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
124 |     brainfuck!(++++++++++[>+++++++>++++++++++>+++++++++++>+++>+<<<<<-]>++.>>+.---.<---.>>++.<+.++++++++.-------.<+++.>+.>+.>.);
    |     --------------------------------------------------------------------------------------------------------------------------- in this macro invocation
    |
    = help: consider adding a `#![recursion_limit="2000"]` attribute to your crate

Here is the macro code:

#[macro_export]
macro_rules! brainfuck {
    (@impl $var:ident;) => {};

    (@impl $var:ident; + $($t:tt)*) => {
        $var.inc();
        brainfuck!(@impl $var; $($t)*);
    };

    (@impl $var:ident; - $($t:tt)*) => {
        $var.dec();
        brainfuck!(@impl $var; $($t)*);
    };

    (@impl $var:ident; > $($t:tt)*) => {
        $var.next();
        brainfuck!(@impl $var; $($t)*);
    };

    (@impl $var:ident; < $($t:tt)*) => {
        $var.prev();
        brainfuck!(@impl $var; $($t)*);
    };

    (@impl $var:ident; . $($t:tt)*) => {
        $var.printVal();
        brainfuck!(@impl $var; $($t)*);
    };

    (@impl $var:ident; , $($t:tt)*) => {
        $var.getInput();
        brainfuck!(@impl $var; $($t)*);
    };

    (@impl $var:ident; [$($t:tt)*] $($ts:tt)*) => {
        while $var.getVal() != 0 {
            brainfuck!(@impl $var; $($t)*);
        }
        brainfuck!(@impl $var; $($ts)*);
    };

    ($($all_tokens:tt)*) => {
        let mut cell = CellData::new();
        brainfuck!(@impl cell; $($all_tokens)*);
    };
}

It is based on expanding methods from a custom struct. The full code compilation problem can be reproduced in this playground

I'm not really confident in this matching:

    (@impl $var:ident; [$($t:tt)*] $($ts:tt)*) => {
        while $var.getVal() != 0 {
            brainfuck!(@impl $var; $($t)*);
        }
        brainfuck!(@impl $var; $($ts)*);
    };

I thought of this [$($t:tt)*] $($ts:tt)* to match portions of code enclosed by [] with whatever tokens have inside, followed by whatever tokens. But I'm not sure if it should work.

I've been dealing with this for some time and I am completly stuck. Any kind of help is welcome. Thanks in advance!

score 2 · Accepted Answer · answered May 05 '19 at 01:30

The last pattern in your macro matches anything, so if your @impl cases fail to match an expected input, the macro will fall back to the last pattern and essentially start over.

Let's make it not match everything to debug the issue. I'll add @start at the start of the pattern:

#[macro_export]
macro_rules! brainfuck {
    // @impl cases elided

    (@start $($all_tokens:tt)*) => {
        let mut cell = CellData::new();
        brainfuck!(@impl cell; $($all_tokens)*);
    };
}

fn hello_world() {
    brainfuck!(@start ++++++++++[>+++++++>++++++++++>+++++++++++>+++>+<<<<<-]>++.>>+.---.<---.>>++.<+.++++++++.-------.<+++.>+.>+.>.);
}

Now we can clearly see what's wrong:

error: no rules expected the token `<<`
   --> src/main.rs:124:71
    |
77  | macro_rules! brainfuck {
    | ---------------------- when calling this macro
...
124 |     brainfuck!(@start ++++++++++[>+++++++>++++++++++>+++++++++++>+++>+<<<<<-]>++.>>+.---.<---.>>++.<+.++++++++.-------.<+++.>+.>+.>.);
    |                                                                       ^^ no rules expected this token in macro call

error: no rules expected the token `>>`
   --> src/main.rs:124:82
    |
77  | macro_rules! brainfuck {
    | ---------------------- when calling this macro
...
124 |     brainfuck!(@start ++++++++++[>+++++++>++++++++++>+++++++++++>+++>+<<<<<-]>++.>>+.---.<---.>>++.<+.++++++++.-------.<+++.>+.>+.>.);
    |                                                                                  ^^ no rules expected this token in macro call

The problem is that the sequences << and >> are a single token in Rust (at least for macro_rules! macros). You can easily fix your macro by adding these rules:

#[macro_export]
macro_rules! brainfuck {
    // ...

    (@impl $var:ident; >> $($t:tt)*) => {
        $var.next();
        $var.next();
        brainfuck!(@impl $var; $($t)*);
    };

    (@impl $var:ident; << $($t:tt)*) => {
        $var.prev();
        $var.prev();
        brainfuck!(@impl $var; $($t)*);
    };

    // ...
}

This reveals another problematic sequence:

error: no rules expected the token `<-`
   --> src/main.rs:136:75
    |
77  | macro_rules! brainfuck {
    | ---------------------- when calling this macro
...
109 |         brainfuck!(@impl $var; $($t)*);
    |                               - help: missing comma here
...
136 |     brainfuck!(@start ++++++++++[>+++++++>++++++++++>+++++++++++>+++>+<<<<<-]>++.>>+.---.<---.>>++.<+.++++++++.-------.<+++.>+.>+.>.);
    |                                                                           ^^ no rules expected this token in macro call

Not shown in your example is ->, which is also a single token. Again, this needs additional rules:

#[macro_export]
macro_rules! brainfuck {
    // ...

    (@impl $var:ident; <- $($t:tt)*) => {
        $var.prev();
        $var.dec();
        brainfuck!(@impl $var; $($t)*);
    };

    (@impl $var:ident; -> $($t:tt)*) => {
        $var.dec();
        $var.next();
        brainfuck!(@impl $var; $($t)*);
    };

    // ...
}

Procedural macros don't have this problem because they always receive punctuation as one Punct for each character. A Punct knows whether it is joint with the next token or not; that's how a macro can tell < < apart from << (because spaces are not tokens). Procedural macros also don't suffer from the recursion limit.

Macro matching tokens recursive expansion

1 Answers1

Linked