Creeping macro expansion - possible exponential time?

[matthiasbeyer]

I am working on the cloudmqtt crate with the test-dsl crate to create some tests. The test-dsl recently got an update to include some fancy macros for argument construction (see here). I am using this macro in here.

Compiling that code never finishes (see further down for rustc log output). It seems to me that the macro expansion, which is recursive, gets slower and slower, as the rustc debug output gets slower and slower.

To get the code and compile it, this should be sufficient:

git clone https://github.com/matthiasbeyer/cloudmqtt
cd cloudmqtt
git fetch origin --tags
git checkout rustc-bug-report-2025-04-03
cargo build --tests

I expected to see this happen: Code compiles.

Instead, this happened: Compilation never finishes.

Meta

rustc --version --verbose:

rustc 1.85.0 (4d91de4e4 2025-02-17)                                                                                                                                                                                                                                                                                                                                                                                                       
binary: rustc                                                                                                                                                                                                                                                                                                                                                                                                                             
commit-hash: 4d91de4e48198da2e33413efdcd9cd2cc0c46688                                                                                                                                                                                                                                                                                                                                                                                     
commit-date: 2025-02-17                                                                                                                                                                                                                                                                                                                                                                                                                   
host: x86_64-unknown-linux-gnu                                                                                                                                                                                                                                                                                                                                                                                                            
release: 1.85.0                                                                                                                                                                                                                                                                                                                                                                                                                           
LLVM version: 19.1.7 

There is no backtrace, because there's no crash.
The last lines of RUSTC_LOG=debug cargo build --tests --verbose are:

 rustc_expand::mbe::macro_rules::expand_macro sp=crates/cloudmqtt/tests/check_cases.rs:14:1: 16:2 (#0), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:9:1: 9:21 (#0), node_id=NodeId(4294967040), name=harness#0                                                                                                                                                              
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:17:17: 17:91 (#9), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:43:1: 43:29 (#0), node_id=NodeId(4294967040), name=harness_collect#0                                                                                       
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:51:9: 55:10 (#10), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:43:1: 43:29 (#0), node_id=NodeId(4294967040), name=harness_collect#0                                                                                       
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:91:9: 95:10 (#11), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:43:1: 43:29 (#0), node_id=NodeId(4294967040), name=harness_collect#0                                                                                       
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:131:9: 135:10 (#12), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/datatest-stable-0.3.2/src/macros.rs:43:1: 43:29 (#0), node_id=NodeId(4294967040), name=harness_collect#0                                                                                     
 rustc_expand::mbe::macro_rules::expand_macro sp=crates/cloudmqtt/tests/check_cases.rs:45:9: 51:10 (#0), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                                                                                    
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#15), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:106:17: 106:75 (#16), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:108:17: 108:87 (#16), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:120:9: 120:83 (#15), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                             
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:125:17: 125:79 (#15), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:127:20: 127:87 (#15), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=crates/cloudmqtt/tests/check_cases.rs:56:9: 61:12 (#0), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                                                                                    
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#27), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#28), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#29), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#30), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#31), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#32), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#33), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#34), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#35), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#36), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#37), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#38), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#39), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#40), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#41), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#42), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#43), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#44), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#45), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#46), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0                                                                                            
 rustc_expand::mbe::macro_rules::expand_macro sp=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:117:13: 117:98 (#47), def_span=/home/m/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/test-dsl-0.3.1/src/macros.rs:67:1: 67:35 (#0), node_id=NodeId(4294967040), name=named_parameters_verb#0   

[TheNeikos]

I'd add that we tried to reduce this, but trying my own complicated invocations of the macro seemed to be completely fine.

Given that the macro itself isn't actually 'infinitely' recursive and instead just invokes itself with special cases (as marked with @tags) I wouldn't expect it to actually cause a hang like this either 🤔

It might have to do with datatest-stable. But that also does not seem suspect. And either way, rustc has a mechanism to detect deep recursion. So it seems that this might be some form of n^2 macro pattern-matching pitfall? (Absolute guess in the dark)

[TheNeikos]

After further attempts of reducing, this is due to this line:

            $crate::named_parameters_verb!(@call __NamedVerb => { $($input)* } => { $($input)* })

Coupled with the fact that the macro is called with an extra token, this causes it to 'fall through' to the base case, which calls it again, thus actually causing a recursive call! But in this situation, the compiler hasn't reached the depths required to error out, while at the same time expanding into millions of lines of code.

I feel like this is still a bug, albeit more wrt diagnostics? As the compiler looks completely unresponsive, and gives no indication to what is causing it. (Despite the error being one of user-code doing something non-sensical)