RE2/J: a Java regex engine that cannot backtrack

Why backtracking turns a regex into a denial of service

The problem RE2/J addresses is not speed, it is worst case behaviour. The standard Java package java.util.regex, along with widely used packages such as PCRE, Perl and Python, use a backtracking implementation strategy. When a pattern offers two alternatives such as `a|b`, the engine tries the subpattern `a` first, and if that yields no match it resets the input stream and tries `b` instead.

That reset-and-retry model multiplies. If the choices are deeply nested, the strategy needs an exponential number of passes over the input before it can decide whether there is a match at all. The README puts it bluntly: it is easy to construct a pattern whose running time would exceed the lifetime of the universe. That turns into a security problem in the specific situation of accepting regular expression patterns from untrusted sources, such as users of a web application. A user typing a pattern into a search box is the classic case.

RE2/J takes the other road. It explores all matches simultaneously in a single pass over the input using a nondeterministic finite automaton. The result is a matcher whose cost is linear in the size of the input, with no input size at which it starts exploring combinations of paths.

A pure Java port of the C++ RE2, not a wrapper

RE2 was designed and implemented in C++ by Russ Cox, and the C++ version includes both NFA and DFA engines along with numerous optimisations. RE2/J is a port of that library to pure Java, so there is no native dependency and no JNI layer to deploy. The lineage is documented in detail, and it explains a lot about the design. Russ Cox also ported a simplified version of the NFA to Go, Alan Donovan ported the NFA-based Go implementation to Java, and Afroz Mohiuddin wrapped the engine in a familiar Java Matcher and Pattern API. James Ring prepared the open-source release and has been its primary maintainer since then.

Two details in that history are worth pulling out. The Java implementation descends from the Go port, which itself descended from a simplified NFA, so it is the NFA side of RE2 that lives in Java, not the DFA engine. And the API surface is a deliberate compatibility layer: the same Pattern and Matcher vocabulary that Java developers already know, backed by a different execution strategy.

That combination is what makes the library usable in an existing codebase. You change the import and the semantics of matching change under you, but the shape of the code does not have to.

Adding RE2/J to a Maven or Gradle build

The documented installation path is a Maven dependency, and the snippet in the README is the whole procedure:

<dependency>
  <groupId>com.google.re2j</groupId>
  <artifactId>re2j</artifactId>
  <version>1.6</version>
</dependency>

The same artifact coordinates work in any build system compatible with the Maven Central repositories, which the README names explicitly, giving Gradle and Ivy as examples. The group and artifact identifiers are `com.google.re2j` and `re2j`, and the version shown in the snippet is 1.6.

There is a second route for people who do not want to touch their build file. The README describes downloading the RE2/J JAR from the project release tag on GitHub and adding it to the CLASSPATH.

For a first use, the pattern is to take one existing java.util.regex call site, swap the package, and run the same pattern against the same input. The repository layout shows a Gradle build with a `java/` source tree, a `javatests/` tree, a `testdata/` directory and a `unicode/` directory, and the README carries build and coverage badges for the master branch, which tells you the project runs a continuous integration build and tracks coverage rather than shipping untested.

One thing to check before you rely on the snippet version: the most recent release tag listed for the project is RE2/J 1.8, published on 2025-01-09, while the dependency snippet in the README still names 1.6. Pin deliberately rather than copying blindly.

The java.util.regex features RE2/J does not implement

This is the part of the README that deserves the closest reading, because it is where migrations break. The documentation is unambiguous: RE2/J is not a drop-in replacement for java.util.regex, and beyond the different package name it does not support the following parts of the interface.

The MatchResult class is absent, and so are Matcher.hasAnchoringBounds(), hasTransparentBounds(), hitEnd(), region(int, int), regionEnd(), regionStart(), requireEnd(), toMatchResult(), useAnchoringBounds(boolean), usePattern(Pattern) and useTransparentBounds(boolean). The pattern flags CANON_EQ, COMMENTS, LITERAL, UNICODE_CASE, UNICODE_CHARACTER_CLASS and UNIX_LINES are missing as well, and PatternSyntaxException.getMessage() is not supported. The documentation adds that there is no parity with the full set of Java character classes and special regular expression constructs.

The practical grouping matters. The region and bounds methods are the ones that break code which anchors a match to a slice of a larger string, a common technique in scanners and log parsers. The missing flags are the ones that change how a pattern is interpreted, and UNIX_LINES in particular changes how line terminators are treated. If your existing code uses any of them, the migration is a rewrite of those call sites, not a package swap.

There is one further functional limit that is not about the API at all. Backreferences cannot be implemented in linear time, and the README states that the vast majority of regular expression patterns in practice avoid such features. If your patterns rely on backreferences, RE2/J is the wrong library and no configuration will change that.

Alternation-heavy patterns are where the switch pays off

The documentation frames the decision to switch in terms of pattern shape. If you use regular expression patterns with a high degree of alternation, the code may run faster with RE2/J. That is a narrower claim than a blanket performance statement, and it is the honest one, because the cost of a backtracking matcher on a well behaved pattern is a small constant, while the cost on a pathological one is unbounded.

The worst case is what the documentation emphasises. The java.util.regex matcher may run forever, or exceed the available stack space and fail, and the README states that this will never happen with RE2/J. Stack exhaustion is worth calling out separately because it fails differently from a hang. A backtracking engine that recurses deeply can throw a StackOverflowError, which is an Error rather than an Exception and will slip past many catch blocks. RE2/J removes that failure mode along with the timeout one.

So the decision rule is about where the pattern comes from. A pattern written by your own team, tested, with no untrusted alternation, is unlikely to hit the problem. A pattern assembled from user input, from a stored search query, or from a configuration field that an operator can edit, is exactly the case the library was built for.

What sits in the repository beyond the engine

The repository layout shows a working project rather than a bare library. Alongside the README, CONTRIBUTING.md and the licence files, there is a Gradle build with build.gradle, settings.gradle, a gradle/ directory and the gradlew and gradlew.bat wrapper scripts, which means the project builds the same way on Linux and on Windows without a system Gradle install. There is a benchmarks/ directory, a testdata/ directory, and a unicode/ directory.

Two of those deserve a mention. A benchmarks directory implies the project carries its own comparison harness, which is where you would look to see how a pattern behaves in each engine, though the README does not publish results from it, and this article makes no claim about measured numbers. The unicode/ directory points at the part of the work that is genuinely hard in a port: character class semantics. That connects directly to the caveat that RE2/J does not have parity with the full set of Java character classes and special constructs.

There is also a RELEASING.md file, which means the release process is written down rather than improvised, and a .github/ directory holding the continuous integration workflow that the build badge in the README points at.

Google ownership, experimental status, and a licence to read yourself

The README states the status plainly: this is not an official Google product, experimental or otherwise, it is just code that happens to be owned by Google. That sentence is the single most important line in the document for an adopter, and it is easy to read past. There is no Google support commitment behind the project, and no Google product roadmap. The maintenance is carried by named individuals in the community, with a discussion group for the RE2/J discussion list and a separate set of instructions for contributors.

The activity level, from what the release history shows, is steady rather than fast. RE2/J 1.8 was published on 2025-01-09, 1.7 on 2022-06-30 and 1.6 on 2021-03-08, and the last push to the master branch was on 2026-05-22. So the code is still being touched, but the gap between release tags is measured in years, not weeks. For a library whose whole selling point is that it will never hang on your input, that is an acceptable cadence, but it is not the cadence of a project shipping weekly.

On the licence, the repository is reported with a custom licence that GitHub cannot classify, and the instruction is to see the LICENSE file. The README does not name a licence in the text quoted here, so this article does not assert one. If the licence terms matter to your organisation, read the LICENSE file in the repository and have your own counsel interpret it. That is a concrete step, and it is the only reliable one.

Editorial conclusion

Adopt RE2/J where a regular expression is built from user input or from a configuration file you do not control, since a backtracking engine can be pushed into exponential time on a nested alternation, and RE2/J removes that failure mode by construction rather than by a timeout. Do not adopt it where you rely on backreferences, region bounds, or the full java.util.regex surface, because the README lists those as unsupported. Before you switch, check your patterns for constructs that cannot be expressed in linear time, and read the LICENSE file in the repository yourself, since the licence reported for it is not one GitHub can classify.

Frequently asked questions

Official sources

1. google/re2j on GitHub
2. Issues
3. README
4. Releases