While poking around rust-analyzer, I noticed that it ports an important algorithm for macro expansion from rustc. While thinking about how I would implement that algorithm myself, I discovered a degenerate edge case that could OOM rustc surprisingly easily. You can read more here: https://bal-e.org/blog/2026/oops-cubic-macro/
Post
Replies:
2
@bal4e Earley parsers can be optimized to run in linear time, but there seems to be only one person in the world who fully understands how to do it, and his implementation (https://savage.net.au/Marpa.html) is in Perl (with a C core library), so nobody outside the Perl community uses it.
@bal4e I'm not an expert on the nuances of Rust macros, but after reading your blog post, it sounds to me like the matching part describes only regular languages. (I think the token-tree rules are what really make this possible, perhaps?) If that's true then, in principle, matching can always be done in time linear in the length of the input. Although the connection with Earley parsing makes sense, the algorithm you describe sounds a little like a Pike-style VM for regular expression matching, and a lot like the implementation from "A Play on Regular Expressions". Do you think regular expression matching algorithms apply here? If that's too restrictive, I'd want to go re-read the "Parsing with Derivatives" papers (by Matt Might, IIRC).
