fancy-regex: backtracking where Rust's regex crate cannot go

The problem: the regex crate cannot express a useful pattern

Rust's regex crate is built on non-deterministic finite automata, and that design choice buys linear-time matching on the length of the input. It also means no backreferences and no look-around, because an NFA cannot express them.

The README gives a concrete example of what is lost. TextMate's syntax definitions, which are based on the Oniguruma backtracking engine, routinely use backreferences and look-around, and those definitions are now used in a number of other editors including Sublime Text and Atom. The pattern shown in the README captures a single-line Rust raw string by matching the opening hash marks and then referring back to them to close the match.

The README states plainly that there is no NFA that can express this simple and useful pattern, and that a backtracking implementation handles it efficiently.

That is the case fancy-regex exists for. It is a Rust library for compiling and matching regular expressions that uses a hybrid implementation to support a relatively rich set of features, and it uses backtracking to implement the fancy features that purely NFA-based implementations, such as RE2 and the regex crate, cannot.

The project description also says it aims to be compatible with Oniguruma syntax when the relevant flag is set, with a dedicated compatibility document listing the current status and known gaps. That document is the first thing to read if your use case is a TextMate grammar, because the gaps are where the compatibility claim stops.

The audience is narrow and well defined: a Rust developer who needs a feature the linear-time engine cannot provide, and who can live with the performance characteristics that come with it.

The two-phase analysis that decides what gets delegated

The mechanism is more interesting than a simple wrapper, and the README describes it in detail.

The library implements a backtracking virtual machine, similar in spirit to PCRE, and then delegates as much work as possible to an inner NFA implementation, which in Rust is the regex crate. A simple approach would be to detect whether the whole pattern contains fancy features and pick one engine or the other, but the README says this module attempts to be more fine-grained and implements a true hybrid approach.

The analysis runs in two phases.

Phase one is a bottom-up analysis of each subexpression, determining three properties. Whether the subexpression is hard, meaning it requires backtracking features such as backreferences, look-around, atomic groups or conditionals. The minimum size, meaning the minimum number of characters the subexpression will match. And whether it is constant size, meaning it always matches the same number of characters.

Phase two is a top-down compilation from the root of the expression, passing a hard context that flows from parent to child. The context indicates whether variations in match length will affect backtracking decisions. When both the subexpression and the context are easy, the compiler emits a Delegate instruction that offloads the work to the NFA engine. Otherwise it emits explicit VM instructions.

There is a further optimisation for concatenations. The compiler identifies a prefix of constant-size easy subexpressions that can be delegated because they will not affect backtracking, and if the context is easy it identifies a suffix as well. The hard middle section is compiled with explicit backtracking instructions, and the hard context flows from right to left, so only the rightmost hard subexpression gets an easy context.

The result is that a pattern with no fancy features behaves primarily as a lightweight wrapper around the underlying engine, and a pattern with fancy features is compiled so that only the awkward parts backtrack.

Feature flags decide what the crate can even parse

The Cargo.toml shows that the feature set is not just about performance, it decides which syntax the library accepts.

The default features are unicode, perf, std and variable-lookbehinds. The variable-lookbehinds feature enables variable-length lookbehinds using reverse DFA search, which means that without it, a lookbehind of variable width is not available.

The rest of the flags are more conventional. perf enables the perf feature of regex-automata, unicode turns on the unicode features of regex-automata and regex-syntax, and std enables the std features of those crates along with bit-set.

Two flags exist for specific semantics and performance profiles. leftmost_longest enables builder support for leftmost-longest match semantics, as opposed to the default leftmost-first, and it exists for callers who need the other match semantics. perf-dfa-full makes regex-automata eagerly build a fully compiled dense DFA for small patterns and for delegated fragments, and the comment in the manifest is honest about the cost: noticeably slower compiles and more memory, traded for the fastest search engine, and without it searches use the lazy DFA which performs about the same on typical workloads. It mirrors the perf-dfa-full opt-in in the regex crate.

The dependency on regex-automata is at version 0.4.16 with a specific set of features enabled: alloc, syntax, meta, nfa, dfa-onepass, dfa-search and hybrid. Notably, the crate pulls in the DFA machinery and the hybrid engine, which is what makes the delegation strategy possible rather than delegating everything to a single NFA path.

The minimum supported Rust version is 1.66, the edition is 2021, and the crate is MIT licensed. The package is published as fancy-regex with API docs on docs.rs.

The performance warning is the most important part of the README

There is a section headed a warning about worst-case performance, and it should be read before the feature list rather than after it.

The argument goes like this. NFA-based approaches give strong guarantees about worst-case performance. For regexes that contain fancy features such as backreferences and look-around, this module gives no corresponding guarantee. And the consequence is stated in plain terms: if an attacker can control the regular expressions that will be matched against, they will be able to successfully mount a denial-of-service attack. The README says be warned.

The example of the exponential blowup comes from a paper on static analysis for regular expression exponential runtime:

import re
re.compile('(a|b|ab)*bc').match('ab' * 28 + 'ac')

The README states that in Python, tested on versions 2.7 and 3.5, this match takes 91 seconds and doubles for each additional repeat of ab. It also says that this package is one of the first that handles both cases well, and that the exponential blowup case above is run in 258 nanoseconds.

That is a specific number from the project's own documentation, and it is worth reading carefully. The hybrid design does solve the classic catastrophic case, because the delegated part goes to the linear-time engine. But the warning still stands for genuinely hard patterns, and PERFORMANCE.md is linked for more examples.

So the honest summary is two different claims. On the pathological patterns that make naive backtracking blow up, this library is fast. On patterns that use look-around and backreferences, there is no worst-case guarantee, and the library is explicit that untrusted patterns are a denial-of-service vector.

Oniguruma compatibility is a goal with a documented gap list

The compatibility story is what makes this library interesting beyond the Rust ecosystem, because Oniguruma is the engine behind Ruby, PHP, and the TextMate grammars that editors use.

The project description says it aims to be compatible with Oniguruma syntax when the relevant flag is set, and points to a document in the docs directory for the current compatibility status and known gaps. The wording is careful: aims to be, with a status document, with known gaps. That is three qualifications in one sentence, and the document is where the specifics live.

The practical consequence for an adopter is clear enough. If you are porting grammars written for Oniguruma, and specifically TextMate syntax definitions, then the compatibility document is the checklist. Gaps in that document are gaps you will hit, and the fix is either a pattern change in the grammar, which you do not control if the grammar belongs to a third party, or a limitation you accept.

The examples directory in the repository is telling. There is a compile_mem example, a toy example, and a syntax highlighting example named regexset_syntax_highlighting. The last one is a direct reference to the TextMate use case, and it is the closest thing in the repository to a worked example of the motivating problem.

The repository also carries a fuzz directory, which is a reasonable inclusion for a library whose matching engine is a backtracking virtual machine. There is a benches directory for benchmarks, a playground directory backing the online playground the README links, an AGENTS.md, a CHANGELOG.md, an AUTHORS file, and a Cargo.lock.msrv file that is excluded from the published package, which is a conventional way of tracking the dependency versions for the minimum supported Rust version separately from the main lock file.

Where fancy-regex is the wrong tool

The first wrong-tool case is a pattern you control. If you can express what you need without look-around or backreferences, the plain regex crate is faster, has a guaranteed linear time bound, and has no exponential failure mode. Reaching for fancy-regex because it is more capable rather than because it is necessary is the most common way to end up with a performance problem that did not have to exist.

The second is any service that matches patterns supplied by users. The README says this directly, and it is not a theoretical concern. A search box that lets a user type a regular expression and then runs it against a large corpus is the exact scenario the warning describes, and the failure is a hung worker rather than a wrong answer.

The third is a project that needs only one of the two features. If you need look-around but not backreferences, or you need backreferences in one small place in an otherwise ordinary codebase, the cost is that the whole library becomes the thing that can blow up. The hybrid design reduces the exposure to the hard parts of the pattern, but it does not remove it.

The fourth is a codebase with a portability constraint. This is a Rust library, and if the work has to move to another language, the Oniguruma compatibility mode is the part that might carry over, but the hybrid delegation machinery does not.

The fifth is a case where Oniguruma compatibility is assumed rather than checked. The compatibility document exists precisely because the gaps are known, and a project that ports a large grammar without reading it will find out about the gaps one broken pattern at a time.

One more practical point. The README's current status section is cut short, saying only that the project is still in development. The releases tell a more useful story: 0.19.0 on 2026-07-28, 0.19.1 on 2026-09-06 and 0.19.2 on 2026-09-13, with the last push on 2026-10-22 and the repository not archived. The version is below 1.0, so the API is not frozen, and the changelog is the file to read when you upgrade.

Editorial conclusion

fancy-regex fits a Rust project that needs backreferences or look-around and cannot rewrite its patterns to avoid them, such as a syntax highlighter consuming TextMate grammars. It is the wrong choice for patterns you control, where the plain regex crate is faster and linear time, and it is dangerous for any service that matches patterns supplied by users. Before adopting it, check the Oniguruma compatibility document for the gaps in your target syntax, read PERFORMANCE.md for the exponential cases, and confirm that no part of your system lets an untrusted party write the pattern.

Frequently asked questions

Official sources

1. fancy-regex/fancy-regex on GitHub
2. License: MIT
3. Project website
4. README
5. Releases