SafeRE 1.0 released

I’ve just released SafeRE 1.0.0, a safe, correct, and fast regular expression library for Java. You can grab it from Maven Central.

SafeRE guarantees linear-time matching for a fixed compiled pattern. SafeRE’s finite automata prevent catastrophic backtracking by construction, blocking regular expression denial-of-service (ReDoS) attacks that exploit it.

What does 1.0 mean?

My initial goal in building SafeRE was to deliver a safe, production-grade regex library using agents to accelerate the process. It was an experiment to see whether I could build a technically complex library faster than previously possible, and a way for me to build experience developing in a serious (i.e., not vibecoded) codebase with agents.

But what does production-grade actually mean? At the beginning of the project, I thought it meant correctness and “good enough” performance, which to me meant rough parity with the JDK. So I spent most of my time on correctness, building a large amount of testing infrastructure — unit and regression tests, differential tests against the JDK, fuzz tests, and exhaustive tests — to make sure SafeRE was as correct as possible (see the section below for what I learned from this). SafeRE’s CI runs over 10 million test cases on each commit, and there are 20 billion additional cases available through on-demand exhaustive sweeps. These days, the differences we find through fuzz testing more often turn out to be JDK bugs than SafeRE bugs. That’s made me pretty confident that SafeRE is, if anything, more correct than java.util.regex.

But as people started testing SafeRE for use in their projects, it seemed that performance was now the adoption blocker. The people evaluating SafeRE expected better performance than whatever regex library they were using, which was often something faster than the JDK, such as RE2 via JNI/FFM or Joni. Beyond aggregate performance, every workload that performs worse in SafeRE at least draws scrutiny, even if we eventually decide it’s an acceptable tradeoff.

So over the past 2-3 months, we’ve focused on performance optimizations. My collaborator Liam Miller-Cushon has been incredibly productive, delivering approximately 80 optimization PRs and sharing real-world workloads we can tune.

SafeRE is now substantially faster than the JDK and RE2/J, and somewhat faster than native RE2, overall on the shared curated workloads in Rebar, a comprehensive regex benchmark suite created by @BurntSushi, the author of ripgrep and Rust’s regex library. You can find the detailed results and methodology in the 1.0 benchmark report.

RE2 sets a high bar; it’s a highly tuned C++ implementation with decades of production use at Google, and its design was the foundation for SafeRE. I’m proud that SafeRE, written in Java, is now a little faster than RE2 on these benchmarks.

That’s what 1.0 means to me: I’m confident SafeRE is ready for production adoption.

What differential testing taught me

I mentioned above that initially I focused on testing and correctness. I built fuzz testing and exhaustive testing tools that compared SafeRE’s results to the JDK and failed when their answers differed. I had assumed that the mature, battle-tested regex implementation in the JDK would be correct pretty much all the time, and any difference in SafeRE’s and the JDK’s answers would indicate a bug in SafeRE.

Initially, this worked well — I found and fixed a lot of SafeRE bugs. But eventually, matching the JDK’s behavior started leading us in directions I wasn’t comfortable with. For example, hitEnd() and requireEnd() report whether a match attempt reached the end of the input and whether more input could invalidate a successful match. While trying to reproduce the JDK’s exact behavior, my agent started reimplementing parts of its backtracking engine! I concluded that reproducing the JDK’s exact behavior likely required backtracking, which would compromise SafeRE’s linear-time guarantee. I also didn’t want SafeRE’s API to depend on details of another engine’s implementation, so I removed support for both methods.

In other cases, I found places where the JDK was returning the wrong answer. Consider this example:

var matcher = java.util.regex.Pattern.compile("(?:(a))*$").matcher("aaab");
matcher.find();

System.out.println(matcher.start());  // 4: end of the input
System.out.println(matcher.group());  // "" (an empty match)
System.out.println(matcher.group(1)); // "a" — should be null

The pattern means “zero or more as, followed by the end of the input.” The parentheses around a capture it; the outer (?:...) just groups the expression without adding another capture.

Because the input ends with b, the only possible match is zero as at the very end. The capturing group never participates in that match, so its value should be null. Instead, the JDK returns "a", left over from an earlier attempt that failed. I reported this as JDK-8381696.

So now I’m in a situation where I’m finding differences, not bugs, via differential testing, and it requires judgement to determine whether there is a bug in SafeRE or the JDK. Furthermore, the regexes that trigger these differences are often weird, which makes sense if you think about it — decades of production use of the JDK have sanded off most of the rough edges people encounter in practice. That left our fuzzers finding increasingly obscure combinations of regex features.

Fixing bugs in weird, rarely encountered regexes is risky, because you can accidentally introduce bugs that would manifest in more commonly used regexes, or you could hurt performance, which has turned out to be critical for adoption.

Right now, I typically fix reported bugs, even minor ones, but I also run benchmarks if the fix looks like it could affect performance. I won’t ship a fix for a rare bug if it causes a performance regression.

On performance optimization

Many of the recent performance optimizations in SafeRE come down to quickly skipping text that cannot match. For example, consider [A-Z]+:\s+[0-9]+: uppercase letters, a colon, whitespace, and a number. If colons are rare in the input, it can be profitable to first scan for colons using Java’s fast String.indexOf method, then check whether the surrounding text satisfies the rest of the pattern. Most of the input never needs to pass through the full regex engine.

HotSpot can accelerate String.indexOf using SIMD instructions, which process multiple values with a single instruction. What if we wanted to write our own algorithms that use SIMD? We can do this using Java’s incubating (experimental) Vector API. While we have not yet found a productive way to use the Vector API with Java Strings without accessing String internals, we have accelerated UTF-8 scanning using the Vector API.

One example is Liam’s implementation of Teddy, an algorithm from Hyperscan that searches for multiple strings at once. For a regex with alternatives like foo|bar|baz, Teddy builds compact fingerprints from the strings and uses SIMD operations to check many input positions in parallel. Most positions can be ruled out immediately. Positions that pass the filter still need to be checked against the actual strings, because the fingerprints can produce false positives. This lets us quickly skip text where none of the alternatives can begin. On our UTF-8 alternation benchmarks with inputs from 1 KB to 100 KB, Liam measured roughly 5-6x speedups over SafeRE before this change.

You can try out the experimental Vector scanner by following these instructions.

Other production considerations

Production users also need a project they can depend on.

To that end, recently I’ve made the following changes:

• Increased the bus factor. For SafeRE to be sustainable, someone else must be able to maintain it. I’ve added Liam as a collaborator, but if it continues to gain adoption, I would consider creating an organization and adding additional maintainers.
• Code reviews. We’ve gotten to the stage of the project where I don’t feel comfortable shipping changes without a second set of eyes on them. Liam has been an amazing partner on this, and I’ve started to run pretty much all my changes by him.
• SNAPSHOT versions for testing. Because SafeRE has been moving pretty quickly, people attempting to integrate it often want the latest version to get the latest performance improvements. So recently I started providing SNAPSHOT builds, which are published on every push to main. See these instructions for how to use them.

What I’ve learned

When I started this project, I naively thought I could build a production-grade safe regex library within a month or two with the help of agents. But it turned out to be much harder than that, even with so many excellent open-source references to learn from and frontier agents to accelerate development. The hard parts are the same parts that would always have been the hard parts for a project like this: matching or exceeding battle-tested, widely used libraries on performance and correctness, while retaining the desired safety guarantees.

On the other hand, a project like this would definitely not be doable or maintainable in my spare time without agents. Not only that, but I’ve enjoyed building with agents and learning how to use them effectively.

Acknowledgements

First, I want to thank my friend and long-time collaborator Liam Miller-Cushon for joining me on this journey. He’s contributed a huge amount to SafeRE, and it’s been a joy to work with him on this project.

I’d also like to thank Mateusz “Serafin” Gajewski for his interest and engagement on behalf of Trino, suggesting the UTF-8 direction, and contributing several optimization PRs.

I also want to thank Kevin Bourrillion for sharing agentic development tips, helping me understand the finer points of Unicode, and patiently listening to me blather on about esoterica like grapheme clusters.

Finally, I want to thank my wife and kids for tolerating my obsession with regexes.
When I was taking a theory of computation course many years ago, I used to lecture my wife (then girlfriend) about regular languages and how you can match a pattern like ab*a quickly by translating it into a finite automaton. Little did she know that decades later I’d still be lecturing her, and now our kids, about the same thing. 🤓

Note: I wrote this post by hand. I used an agent for proofreading and feedback.