what is the status of compile-time regex support?

[BurntSushi]

Originally asked by @sam0x17:

What is the current status of compile-time regex support (last I checked this was developed separately in the regex-automata crate) and what barriers exist currently for bringing this functionality into the main release?

Do the recent improvements in terms of what const fns can do in stable Rust make it feasible to do compile-time regex via const machinery, and has any work been done in that direction? If not, what features would need to be added to const eval contexts to enable this?

With the recent absorption of once_cell into std, do you think there is a path forward for regex eventually becoming part of the rust standard library? If not, why, especially considering the fact that most languages include some sort of regex facility built into the language?

Anyway, love your work!

[BurntSushi]

So this question has a lot of dimensions. The top-line question of the current status though is that "compile-time regex support" is not something I personally am currently working on and don't plan to work on it any time soon.

Other than that, the broad version of this question (just "how to support compile-time regexes") is quite difficult to answer. The issue is that there are a lot of different use cases and different ways to implement something approximating "compile-time regex." For example, a lot of people actually just care about whether static analysis can tell them that their regex is valid, but otherwise don't care so much that it's actually build when the Rust program is compiled. That can be (and is) satisfied by a Clippy lint. Otherwise, the broad version of the question is explored a bit in this meandering discussion on the topic.

The narrower version of this question, "is it possible for Regex::new to be const fn," is easier to answer. The short answer is that my approximation is that of the approximate 100K lines of code that make up the regex crate and its dependencies, probably about two thirds of it is code that runs during Regex::new. So for Regex::new to be const, you really need the vast majority of the Rust language to be usable inside a const context. Notably, that includes interior mutability, dynamic memory allocation, generics and probably other interesting things. So the answer to this question is another question, "when will the majority of the Rust language be usable in a const context?" I don't know the answer to that, but "never" or "no time soon" is a plausible guess. But I don't really have a ton of context on the const roadmap.

A nerdier version of the question is perhaps something like this: "Okay okay, so the regex crate's current implementation can't be used in a const fn, but would it be possible to change the implementation such that it is limited to things that can be used in const context either today or Real Soon Now?" I'm not sure of the answer to that question. I'm pretty certain the answer is, "given the requirements of the regex crate, no, it could not be done." But there is some measure of creativity in answering that question that I don't want to under-estimate.

And an even nerdier version of that is, "is it possible to build any regex engine such that Regex::new would be const using existing-or-soon-to-be const support?" I would guess it might be possible to build such a thing, but I would guess you'd need to give up some things. Likely at the very least optimizations and, perhaps to a significant extent, code readability and abstraction. But I don't want to say it's impossible because what qualifies as a "regex engine" is incredibly broad and some folks can be really creative in what you can do in a limited context such as const in Rust.

As for whether regex will ever be in std, I think that stands on its own enough and is common enough that it deserves its own question. See: #1077

[sam0x17]

Yeah, to be fair, the proc-macro approach is definitely easier. I was able to do it seamlessly in my (now abandoned) web framework using regex-automata and some custom proc and attribute macros.

For me, compile-time regex support was important at the time because I was going to be deploying to serverless contexts, so it would have been bad to have to re-compile the regex set for all routes (or even memoize it in a static) for every new lambda that is created.

Someday I'd love to re-visit this though and either make a proc/attribute macro veneer for regex-automata for you, or try to undertake doing a ground-up build of a compile-time-oriented regex approach.

Personally I'm the sort who can't stop thinking of the CPU cycles spent at runtime compiling a regex that could have been compiled at compile-time, especially when compared with other systems languages that pre-compile these.

Anyway thanks for all the info!

[BurntSushi]

Yeah the problem there is that approach compiles a full DFA. That is both incredibly expensive and resource hungry, even when done at compile time. A good compile time regex solution, IMO, would support building just a thompson NFA and then using that. But that's where things get really tricky, because you need to support that sort of thing all throughout regex-automata.