The state of the procedural code generation in Rust
Long story short: it is impossible to generate reliable and fast code for a DFA recognizer in Rust.
The reason why it's impossible is simple: Rust supports neither goto nor tail call elimination. So it's impossible to represent a code with advanced control flow. And even though Rust has MIR which supports goto, it is unavailable from the procedural macros side.
The state of the art lexer for Rust, Logos uses tail calls to represent transitions between states (example). It quite fragile obviously, since there's no guarantee of tail call elimination in Rust (though LLVM can optimize it). But it seems to be the only way to achieve a reasonable performance.
It's quite unfortunate that I will probably have to go the same route for my own lexer generator as well.
Posted Jun 21, 2020, 12:22 PM UTC
The normal solution to this is to have an enum with one alternative for each state. Then you write a loop that switches/matches on the enum value, and you goto by assigning the value matched upon on each loop, optionally with a continue to force the early restart. It's slightly less efficient in that you have an indirect vs direct branch for each time around the loop.
It can be less efficient, but I fed some simple examples to godbolt and saw it generate direct jumps between states.