Tail-call optimization in macro expansion

#1

I’m woefully ignorant about the internals of the macro system, so I don’t know if this is conceptually or practically impossible in the current implementation.

But if it’s not, I’d like to point out that tail-call optimization would go a long way towards making macro_rules! almost as powerful as procedural macros. The well-known TT munching and stack/queue argument manipulation techniques would especially benefit from it. It would make it possible to parse much more varied DSLs and still be easier to write and arguably more readable than procedural macros (or not.)

In any case, this is currently a serious limitation of the macro system, considering it’s a language without any looping constructs.

What would it mean to add this feature? Is it something a beginner Rust hacker can attempt? Are there any known roadblocks?

#2

What does the tail call optimization do for macro expansion specifically? As far as I understand, macro expansion is already “stackless”.

#3

The expander is stackless, in the sense that it doesn’t use the stack, but it still uses heap for each recursive tail call. This limits the capacity to use tail recursion in macros as a replacement for loops, to implement all sorts of compile-time algorithms and parsers.

But that PR you linked is actually a great starting point! Thanks. I’m going to study it and see if I can improve the code.

The goal would be for the recursion limit to only apply to non-tail calls and to be much higher.

#4

Huh, a very good point. It would certainly be easier to do tail recursion in this context.

Currently we use a “max depth” counter to prevent infinite recursion and ensure termination. This may or may not be a good idea; at minimum, this should probably be hygienic, as well, so that a crate can declare a max depth (or the absence of one) for its macros, and this would be respected by downstream crates without them having to repeat it.