However! One of the neat things about Workers is that you totally can use regexes in JavaScript, and our sandbox prevents runaway CPU usage. So if you really wanted regex-based page rules before, you can probably get that with a Worker.
We've exposed an API for controlling Cloudflare features from a Worker, including many things commonly controlled via page rules:
https://developers.cloudflare.com/workers/reference/cloudfla...
We'll be adding more in the future.
Would that still be true if you limited the regex support to DFAs instead of NFAs? I can’t think of a single use-case for backreferences in routing patterns. :)
NFAs and DFAs have equivalent expressive power[1]. For this application, you probably want a determinized DFA (one without epsilon transitions); that's constant time on the input string. (It's still not as fast as Boyer-Moore.)
Backrefs let you write PDAs, which are more powerful than either NFAs or DFAs.
PCRE2[2] implements DFA-based matching. The cited page says it's slower than the NFA algorithm (although presumably a lower complexity order); I think because of lookaheads and capturing.
[1] Michael Sipser, _Introduction to the Theory of Computation_.
Yep, that's the thing I was thinking of. Thanks!
Question, since you seem like you might know: is there an alternative regex library—or a plain Yacc parsing grammar that you could stick as a validator in front of PCRE's parser—that would allow through only the regexes which parse out to constant-time (determinized) DFAs?