IIRC, that's what the Rust regex engine[1] currently uses
I am at least currently not aware of any "production" and "general purpose" regex engine that is built on derivatives. And I'm not really sure how you'd build one. The biggest hurdle you'd have to over come as far as I can tell is that derivatives are usually used to build a DFA. In this case, the OP does matching while taking the derivative simultaneously. My guess is that you'll run into problems doing that which huge character classes, which are easy to get when Unicode is enabled.
Whether "production" and "general purpose" are the same as "practical" is unclear. To put away the vague words, my understanding is that with derivatives, you'll either get slow match times or slow compilation times. (To the point where "slow" becomes enough to notice and be a problem.)
With that said, the world is full of experts saying you can't do something. What I'm trying to say here is that there are some challenges I've faced in the course of building a regex engine that I simply don't know how I'd address with derivatives.
Another thing worth considering here is the match semantics of the regex. I haven't had time yet to try this particular matcher, but when I do, I'd check for how alternations are matched. For example, what does 'samwise|sam' match in the haystack 'samwise'? Either answer is correct, but one is typically found in POSIX engines and the other found in Perl-like engines. Can derivatives implement either?
It's also worth noting that I am not an expert on regex derivatives. I've never actually build a derivative oriented matcher. If I had, I'm sure I could be a lot more specific with my criticisms. :-)
PCRE semantics was indeed the big thing that required new techniques. Basically, you have to modify the derivation function such that the derivatives model what paths through the pattern a backtracking engine would consider before stopping at the current position.
The big thing derivatives buys you is the ability to apply rewrite rules lazily during the construction. For example, when we can prove that a regex R subsumes a regex T, then an alternation R|T can be rewritten to just R, since T is already included in it. These kinds of rewrites often result in the DFA that gets constructed being minimal or close to so. Of course, you do pay somewhat for the machinery to do this, so best-case construction times suffer compared to in traditional NFA+lazy-DFA engines like RE2 or Rust's, but a larger class of patterns get to stay in the DFA world with derivatives.
I hope our work ignites a new interest in regex matching with derivatives. I believe the ability to apply these syntactic rewrites on-the-fly is really powerful and I'd love to see how far folks like you with extensive experience in optimizing regex matchers can take this.
> For example, when we can prove that a regex R subsumes a regex T, then an alternation R|T can be rewritten to just R, since T is already included in it.
This doesn't compose though, right? For example, if you have `sam|samwise`, then you can do that transformation, but if you have `\b(?:sam|samwise)\b` then you can't.
> but a larger class of patterns get to stay in the DFA world with derivatives.
Can you say more about this?
>This doesn't compose though, right? For example, if you have `sam|samwise`, then you can do that transformation, but if you have `\b(?:sam|samwise)\b` then you can't.
You'd get subsumption when you have something like '(?:sam)?wise|wise' and in fact this kind of subsumption due to a "nullable prefix" is the main one currently detected (because we encountered patterns that motivated it). And you're right that all these rewrites should compose regardless of context so that they can be eagerly applied in the AST constructors.
>> but a larger class of patterns get to stay in the DFA world with derivatives. >Can you say more about this?
Yeah, the easiest example I can point at is from that tool paper [1], where a subsumption-based rewrite for counted repetitions can turn an exponential blow-up into a linear one. Off the top of my head I think a pattern like '.*a[ab]{0,1000}' would have a 2^1000 blow-up when determinized into a DFA but stays linear in size with derivatives. However, that loop subsumption rule isn't valid as-is under PCRE semantics, so it still needs some work to be ported to the .NET engine.
Before we get that PLDI paper out the best resource is probably just the code under [2]. It's fairly well commented, but of course that's no substitute for a good write-up.
[1]: https://www.microsoft.com/en-us/research/uploads/prod/2019/0... [2]: https://github.com/dotnet/runtime/tree/main/src/libraries/Sy...
If anyone wants to add this Ocaml engine to the harness (or any other engine), please email me at jamslam@gmail.com and I'll give access to the repo. The only reason it isn't public yet is because I'm still working on the initial release and iterating. But it's close enough where other people could submit benchmark programs for other regex engines.
It's actually easy to compute classes of characters that have the same derivative (it's done in the linked "Regular-expression derivative re-examined" paper, although their particular implementation favors simplicity over efficiency), and it's not even necessary when using Antimirov's partial derivatives.
Actually, the complexity of the derivation is independent of the size of the alphabet. You could even define derivation on an arbitrary semi-lattice, not necessarily a set of characters. (Or a boolean algebra if you care about negation/complementation).
The difficulty in handling unicode has more to do with the efficiency of the automaton representation and manipulation rather than in turning the RE in an NFA or DFA.
It has been a long time since I read the "Regular-expression derivative re-examined" derivative paper. Mostly the only thing I remember at this point is that I came away thinking that it would be difficult to adapt in practice for large Unicode classes. But I don't remember the details.
It is honestly very difficult for me to translate your comment here into an actionable implementation strategy. But that's probably just my inexperience with derivatives talking.
I don't know any besides ocaml-re that Drup already linked, sorry :).
And sorry that my comment is hard to decipher. I think the core point is that the "character set" can be an abstract type from the point of view of the derivation algorithm. So it doesn't matter how they are represented, nor "how big" a character set is.
With Antimirov's derivative (which produces an NFA), there is no constraint on this type.
With Brzozowski's derivative, you need at least the ability to intersect two character sets. So the type should implement a trait with an intersection function (in Rust syntax, `trait Intersect fn intersect(self, Self) -> Self`). That's necessary for any implementation generating a DFA anyway.
And if you also want to deal with complementation, then a second method `fn negate(self) -> Self` is necessary.
I do wonder if there is some room for derivatives in a meta regex engine (like RE2 or the regex crate). For example, if it let you build a DFA more quickly (in practice, not necessarily in theory), then you might be able to use it for a big subset of cases. It's tricky to make that case over the lazy DFA, however, a full DFA has more optimization opportunities. For example, identifying states with very few outgoing transitions and "accelerating" them by running memchr (or memchr2 or memchr3) on those outgoing transitions instead of continuing to walk the automaton. It's really hard to do that with a lazy DFA because you don't really compute entire states up front.
(There’s a thing called “partial derivatives”, which is to Brzozowski derivatives as NFAs are to DFAs, but it doesn’t interact well with intersection and negation if you want to support those.)
Though there is an implementation that relies only on Brzozowski derivatives: https://github.com/google/redgrep