Regex: badly needs fuzzing

That's quite a leap. It's not as if the world is C, C++, and Rust. The community behind any managed language is going to include not just people who've never used C++, but also plenty who have, and who reject it for the same reasons that motivate the Rust folks try their hand at doing better.

For a content filtering/scanning service.

By the time we wrapped up this project Intel finally released Hyperscan as Open Source. Hyperscan implements these and other transformation tricks, not to mention the SIMD optimizations.

However, Hyperscan doesn't have as strong compatibility for PCRE as what we ended up with--100% effectively--and would have necessitated keeping libpcre as a failover. Hyperscan is substantially faster than Ragel for small-to-medium length expressions thanks to their SIMD optimizations, but with huge, unioned expressions (larger than what Hyperscan can handle) Ragel-generated code is on par.

Starting from scratch today and presuming Hyperscan is still well-maintained, it would be most practical to build a solution around Hyperscan. Especially if you need capturing, as capturing expressions can't be unioned effectively. Ragel, however, makes a ton sense for many other tasks than merely speeding up PCRE matching.

What makes Ragel unique is:

1) The way it integrates with the host language (C, C++, Java, etc). It allows executing host-language expressions at state machine transitions. It doesn't directly tie into the host language typing model (e.g. like Boost's template-based regular expressions), but for various reasons it's hardly a liability and often an asset.

2) It allows yielding and resumption of matching at any and all input stream boundaries, with runtime machine state being a simple integer. (Application keeps any additional state however it wants.) Most regular expression tools require a complete string to match against, while a Ragel machine can be iteratively applied to an infinite stream of data. That capability wasn't useful in this scenario, but it's extremely useful for concisely, performantly, and securely implementing network protocols, for example. In a low-level language like C, and especially with asynchronous I/O, this can drastically simplify the task of I/O and buffer management. You could parse (if you wanted) an entire HTTP stream in a single logical pass, without having to deal with line buffering, header continuations, etc as separate concerns in your code, greatly simplifying networking code. In a some sense it can be thought of as a complement if not an alternative to callback schemes, futures/promises, or green threading (a la Go).

And I dislike it when it locks up, yes.

Less impactful than a server-side DoS, but still decidedly ungood.

> "Maybe we should rewrite it in Rust and compare"

That already happened, almost three years ago.

It's an interesting comparison point. The OP contains memory corruption bugs in C++'s standard regex library. If Rust claims to prevent these kinds of bugs, does it actually hold up to scrutiny? One way of testing that is throwing a fuzzer against a regex library written in Rust.

(Hyperscan team lead here)

Interesting. I should point out that Hyperscan is not abandonware; it is still maintained by Intel.

Streaming is not unique to Ragel.

You're not wrong about libpcre compatibility. We have very tight syntactic compatibility with libpcre (that is, we won't misidentify an unsupported construct and supply some erroneous semantics) but we make no secret of our inability to handle general lookarounds and backreferences.

I'm interested in how you went about handling backreferences in Ragel. They have been in our 'too hard' basket for years, although many instances of backrefs are tractable in our framework. It's always seemed easier to not do any of them rather than handle just a few.

Ragel certainly ties into the host language differently, and more tightly, than Hyperscan. We use it ourselves, to lex regexes on the way into Hyperscan, as it happens.