Macro_rules: any way to perform cartesian product without recursion?

help
1

Suppose I'm working on a cfg_if-like macro.

// this invocation (pseudo-example)
m! {
    #[cfg(a, b)] => {
        fn foo() {}
        fn bar() {}
    }
}

// expands to this

#[cfg(a, b)]
fn foo() {}

#[cfg(a, b)]
fn bar() {}

A naive approach might be along these lines:

macro_rules! m {
    // IMPORTANT: I know I could use `$attr:meta` here.
    // This example is just to model the situation I encounter occasionally,
    // and I can't always sidestep it like that.
    (#[$($attr:tt)*] => { $($items:item)* }) => {
        $(
            #[$($attr)*]
            $items
        )*
    }
}

This doesn't appear to be a valid syntax:

error: attempted to repeat an expression containing no syntax variables matched as repeating at this depth
 --> src/lib.rs:4:16
  |
4 |             #[$($attr)*]
  |                ^^^^^^^

error: aborting due to previous error

The only working way to do that I'm aware of is to use a "muncher":

macro_rules! m {
    (#[$($attr:tt)*] => { $item:item $($rest:item)* }) => {
        #[$($attr)*]
        $item
        
        m!( #[$($attr)*] => { $($rest)* } );
    };
    
    (#[$($attr:tt)*] => {}) => {};
}

This approach has some disadvantages:

  • Recursive calls can hit the default depth limit (128) for large invocations, requiring downstream crates to increase it.
  • For complex macros, it quickly becomes hairy and hard to read and debug.

So does somebody know a good way to perform cartesian product without recursion?

2

It should always be possible to pack up your list into a single token tree. (Which then solves the problem analogously to your $attrs:meta approach.) Perhaps one preprocessing and one postprocessing step is needed but then you can do it without recursion within a constant depth 3. In your particular example the [$($attr:tt)*] already is a single token tree, and it can also be placed into the output just like that, so no preprocessing or postprocessing is needed.

Edit: I'm not sure my answer is correct. I will check once I'm no longer in mobile.

Edit2: My approach does work.

1 Like
3

There are only two ways to handle sequences with macro_rules! macros:

  • The $( ... )* sequences;

  • Head-Tail recursion.

And as you have noticed, you can't perform cartesian product with $( ... )* sequences.

So that leaves you with Head-tail recursion, and answering "No" to your thread :grimacing:.

That being said, your post is very XY-oriented (which is good, it lets us help you with alternative solutions).

XY - Alternative solutions

1 - Avoid matching a repetition

If you use-case is exactly #[cfg(...)], know that you can handle the contents inside the #[_] with $attr:meta, or even cfg $cfg:tt for this special case:

macro_rules! m {(
    #[$attr:meta] => { $($item:item)* }
) => (
    $(
        #[$attr] $item
    )*
)}

2 - Use recursion

You implemented that in your post, and is honestly not that bad, so it should not be dismissed

3 - Use a procedural macro

Those let your write Rust code to handle the logic for transforming the input into an output, and thus you end up with multiple Vecs or iterables, from which you can generated an iterator with the cartesian product.

4

I think "Yes" is the more correct answer. Here’s an example:

#![feature(trace_macros)]

trace_macros!(true);
macro_rules! product {
    ($($e1:expr),* ; $($e2:expr),*) => {
        product_helper_1!([$([$e1])*][$([$e2])*])   
    }
}
macro_rules! product_helper_1 {
    ([$([$e1:expr])*]$e2:tt) => {
        product_helper_2!($([[$e1]$e2])*)
    }
}
macro_rules! product_helper_2 {
    ($([[$e1:expr][$([$e2:expr])*]])*) => {
        [$($(($e1 + $e2)),*),*]
    }
}

fn main(){
    dbg!(product!(0,10,20,30,40,50; 0,1,2,3,4,5,6,7,8,9));
}

(playground)

Output:

   Compiling playground v0.0.1 (/playground)
note: trace_macro
  --> src/main.rs:21:5
   |
21 |     dbg!(product!(0,10,20,30,40,50; 0,1,2,3,4,5,6,7,8,9));
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: expanding `dbg! { product ! (0, 10, 20, 30, 40, 50 ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) }`
   = note: to `match product!(0, 10, 20, 30, 40, 50 ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
           {
               tmp =>
               {
                   $crate :: eprintln !
                   ("[{}:{}] {} = {:#?}", $crate :: file ! (), $crate :: line ! (),
                    $crate :: stringify !
                    (product!(0, 10, 20, 30, 40, 50 ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)), &
                    tmp) ; tmp
               }
           }`
   = note: expanding `eprintln! { "[{}:{}] {} = {:#?}", $crate :: file ! (), $crate :: line ! (), $crate ::
           stringify ! (product!(0, 10, 20, 30, 40, 50 ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)),
           & tmp }`
   = note: to `{
               $crate :: io ::
               _eprint($crate :: format_args_nl !
                       ("[{}:{}] {} = {:#?}", $crate :: file ! (), $crate :: line ! (),
                        $crate :: stringify !
                        (product!(0, 10, 20, 30, 40, 50 ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)),
                        & tmp)) ;
           }`

note: trace_macro
  --> src/main.rs:21:10
   |
21 |     dbg!(product!(0,10,20,30,40,50; 0,1,2,3,4,5,6,7,8,9));
   |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: expanding `product! { 0, 10, 20, 30, 40, 50 ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }`
   = note: to `product_helper_1 !
           ([[0] [10] [20] [30] [40] [50]] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]])`
   = note: expanding `product_helper_1! { [[0] [10] [20] [30] [40] [50]] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]] }`
   = note: to `product_helper_2 !
           ([[0] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
            [[10] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
            [[20] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
            [[30] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
            [[40] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
            [[50] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]])`
   = note: expanding `product_helper_2! { [[0] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
           [[10] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
           [[20] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
           [[30] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
           [[40] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]]
           [[50] [[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]]] }`
   = note: to `[(0 + 0), (0 + 1), (0 + 2), (0 + 3), (0 + 4), (0 + 5), (0 + 6), (0 + 7),
            (0 + 8), (0 + 9), (10 + 0), (10 + 1), (10 + 2), (10 + 3), (10 + 4), (10 + 5),
            (10 + 6), (10 + 7), (10 + 8), (10 + 9), (20 + 0), (20 + 1), (20 + 2),
            (20 + 3), (20 + 4), (20 + 5), (20 + 6), (20 + 7), (20 + 8), (20 + 9),
            (30 + 0), (30 + 1), (30 + 2), (30 + 3), (30 + 4), (30 + 5), (30 + 6),
            (30 + 7), (30 + 8), (30 + 9), (40 + 0), (40 + 1), (40 + 2), (40 + 3),
            (40 + 4), (40 + 5), (40 + 6), (40 + 7), (40 + 8), (40 + 9), (50 + 0),
            (50 + 1), (50 + 2), (50 + 3), (50 + 4), (50 + 5), (50 + 6), (50 + 7),
            (50 + 8), (50 + 9)]`

    Finished dev [unoptimized + debuginfo] target(s) in 0.82s
     Running `target/debug/playground`
[src/main.rs:21] product!(0, 10, 20, 30, 40, 50 ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) = [
    0,
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10,
    11,
    12,
    13,
    14,
    15,
    16,
    17,
    18,
    19,
    20,
    21,
    22,
    23,
    24,
    25,
    26,
    27,
    28,
    29,
    30,
    31,
    32,
    33,
    34,
    35,
    36,
    37,
    38,
    39,
    40,
    41,
    42,
    43,
    44,
    45,
    46,
    47,
    48,
    49,
    50,
    51,
    52,
    53,
    54,
    55,
    56,
    57,
    58,
    59,
]
5 Likes
5

@Yandros No XY problem involved :smile: This post is a thought exercise - just bringing up a situation I've encountered more than N times and seeing how the hivemind will improve my solution (it has).

And no, no discounting the muncher, that's a handy tool.

@steffahn Cool! I swear I had thought about it, but discarded after I was mislead by Rust reference

When forwarding a matched fragment to another macro-by-example, matchers in the second macro will see an opaque AST of the fragment type. The second macro can't use literal tokens to match the fragments in the matcher, only a fragment specifier of the same type. The ident , lifetime , and tt fragment types are an exception, and can be matched by literal tokens. The following illustrates this restriction:

I thought that if I had a meta token, then it couldn't be matched by $(tt)* down the line. By the piece seems to apply only to literal tokens like foo and not metavariables like $foo:meta .

6

The details of those restrictions are quite subtle. You can still do a lot of things, im particular you can

  • do anything to a value that was only parsed as tt (e.g. you can take it apart into smaller fragments, try parse those fragments or the whole thing as anything else, etc.)
  • parse anything as tt even if it was already parsed as expr or whatever - however in this case e.g. a whole pre-parsed expr, like a+b or f(x) will count as a single tt
1 Like
7

I stand corrected, that's a neat trick! I knew there had to be some recursion involved, but my mistake was to think that that would lead to a muncher / a recursion along all the "axis" / dimensions but one. Recursing along the (fixed) number of dimensions is so powerful, nice! :ok_hand:

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.