REAL

Linear-time, ReDoS-safe C++20 regex with bounded lookarounds — RE2's safety plus the lookarounds RE2 can't do — and a drop-in re-compatible Python binding.

Regular Expression Algorithmic Library — a header-only C++20 regex engine, constexpr from end to end, with an re-compatible Python binding.

• Linear time, always. The engine is a Pike VM (Thompson NFA simulation): no backtracking, ReDoS-safe by construction.
• Constexpr-friendly. Patterns known at compile time are parsed, compiled and matched at compile time.
• Minimal memory. Static (sizes fixed at compile time, zero allocation), dynamic (storage sized exactly once at pattern compilation), or hybrid (compile-time pattern, runtime text, zero heap allocation).
• Zero dependencies. One include.

The problem

Backtracking engines — PCRE, std::regex, Python re — are vulnerable to ReDoS: a pattern like (a+)+b takes exponential time on a hostile input. The linear-time engines that fix this — RE2, Rust's regex — buy safety by dropping lookarounds entirely.

REAL gives you both: linear-time, ReDoS-safe matching with bounded lookarounds.

How it compares

	REAL	std::regex	RE2	Rust regex	PCRE2-JIT	Python re
Linear-time, ReDoS-safe	✅	❌	✅	✅	❌	❌
Lookarounds	✅	✅	❌	❌	✅	✅
Header-only, zero-dependency	✅	✅¹	❌	❌	❌	—
Constexpr (compile-time match)	✅	❌	❌	❌	❌	❌
Drop-in Python re	✅²	❌	❌	❌	❌	✅
Raw throughput	fast³	5–28× slower⁴	3–9× slower	mixed⁵	fast	slow

¹ part of the C++ standard library. ² for the supported subset (no backreferences, etc.). ³ REAL now beats PCRE2-JIT on class scans ([a-z]+ 1.9×, [0-9]+ 1.7×); PCRE2-JIT still leads on straight-line literals / alternation. ⁴ backtracking — 4.1 s where REAL takes 0.5 ms on a (a+)+b-style input: the ReDoS-safety property, quantified, not an adjective. ⁵ not one verdict: REAL leads class scans (5–6×) and dense-capture extraction (3–6×); the crate leads straight-line literal / alternation (1.1–1.3×) and word-boundary; no-match is ≈ parity (1.6×). The per-line duel is in §E. Exact multipliers, machines and methodology are in docs/BENCHMARKS.md.

Every other engine that has lookarounds backtracks (ReDoS-unsafe), and every linear-time engine drops them — REAL is the only one with both: bounded lookarounds and linear-time, ReDoS-safe matching.

ReDoS, in numbers

The classic catastrophic-backtracking pattern (a+)+b over "a"×N (no b, so no match):

engine	input	time
REAL	N = 100 000	0.52 ms — linear
RE2	N = 100 000	0.16 ms — linear
std::regex	N = 26	4107 ms (libstdc++ backtracks; libc++ refuses at "complexity … exceeded")
Python re	n = 24	1398 ms — and climbing exponentially

REAL and RE2 stay linear; the backtracking engines refuse or blow up at trivially small inputs. These figures are from docs/BENCHMARKS.md §C; they depend on the platform, pattern and input, so reproduce them locally with make bench-engines rather than trusting a number here.

Quickstart

Python — pip install real-regex, drop-in for the supported re subset:

import real as re                  # drop-in for the supported re subset
re.search(r"\d+", "x42")           # -> a Match; findall / finditer / sub / split too

C++ — header-only, C++20:

find_package(real CONFIG REQUIRED)
target_link_libraries(app PRIVATE real::real)

#include <real/real.hpp>
real::regex re("[0-9]+");
re.search("x42").matched();        // true

More runnable programs — including the ReDoS demo — are in examples/.

Installation

Channel	Command
PyPI (Python + headers)	pip install real-regex
Homebrew (macOS / Linux)	brew install RECHE23/sci/real-regex
vcpkg	via the vcpkg-sci registry → "dependencies": ["real-regex"]
CMake FetchContent	FetchContent_Declare(real GIT_REPOSITORY https://github.com/RECHE23/real-regex GIT_TAG v2026.6.18)
Vendored	copy include/ and compile with -std=c++20 -I include

REAL is header-only, so "installing" just places the headers and the package metadata where a consumer can find them. After cmake --install <build> --prefix <prefix>, there are three ways to consume it from C++:

# 1. CMake — find_package against the installed config package:
find_package(real CONFIG REQUIRED)
target_link_libraries(app PRIVATE real::real)

# 2. pkg-config — for Make / Meson / autotools (and the system packagers):
c++ -std=c++20 $(pkg-config --cflags real) app.cpp -o app

# 3. Direct copy — vendor include/ into your tree, no build system needed:
c++ -std=c++20 -I/path/to/real/include app.cpp -o app

real::real is also available without installing, via add_subdirectory or FetchContent.

REAL requires C++20 or later. Every header asserts it (#include <real/...> fails fast with a clear message under an older standard), and pkg-config has no field to convey a language standard — so the consumer must pass -std=c++20 (or newer) itself, as shown above.

The header-only library builds and installs with nothing but a C++20 compiler and CMake. The SciForge test harness is needed only to build the test suite (BUILD_TESTING=ON, the default for development and CI), the Python binding and the CI scripts — never the library. Packagers configure with -DBUILD_TESTING=OFF to install the library alone, with no SciForge dependency.

The Homebrew formula consumes the library via CMake find_package(real), pkg-config --cflags real, or -I"$(brew --prefix real-regex)/include" — see the tap README for usage.

Documentation

• API reference & design (Doxygen — "How REAL Works", the internals tour): https://reche23.github.io/real-regex/
• Performance — the measured baseline, with the machine and engine versions and the rust-crate duel: docs/BENCHMARKS.md
• Compatibility (re and std::regex) — the supported subset and every intentional divergence: docs/COMPATIBILITY.md
• Tests & conformance — the differential harnesses and the coverage/gate policy: docs/TESTS.md
• Python — pip install real-regex, the re drop-in: on PyPI.

make python-bench compares throughput against Python's re, and make bench-engines against std::regex, PCRE2 and RE2 in one C++ process (match counts checked equal). Figures depend on the platform, pattern and input — reproduce them locally rather than trusting a number here. The GitHub releases page is the changelog.

Supported syntax

Syntax	Meaning
abc	literal bytes (UTF-8 patterns match their UTF-8 bytes)
\. \* \\ …	escaped metacharacter, matched literally
.	any codepoint except \n
[abc] [a-z] [^abc] [é] [à-ÿ]	character class, ASCII and non-ASCII code-point members / ranges (str mode); [^…] matches any code point outside the set
\w \W \d \D \s \S	word / digit / space classes — Unicode in text mode (like re), ASCII in bytes mode or under a
\n \t \r \f \v \a \0 \xHH	control and hex escapes
x* x+ x?	quantifiers (greedy; append ? for lazy)
x{n} x{n,} x{,m} x{n,m}	counted repetition (greedy or lazy; counts capped at 1000)
a\|b	alternation, leftmost branch preferred
(…) (?:…)	capturing / non-capturing group
(?P<name>…) (?<name>…)	named capturing group (Python and .NET styles)
^ $	line/text anchors (Python semantics: $ also matches before a final \n)
\A \Z	strict text start / end
\b \B	word boundary / non-boundary (Unicode word characters in text mode, ASCII in bytes mode or under a)
\< \>	start / end of word (REAL extension, not in Python re)
(?imsxa) prefix	global flags: i case-insensitive (Unicode fold in text mode), m multiline, s dotall, x verbose (ignore unescaped whitespace and # comments outside classes), a ASCII (re.A: keep \w \W \d \D \s \S \b \B \< \> and icase folding ASCII, even in text mode) — also real::flags on the constructor

Bounded lookarounds match in linear time — REAL's differentiator: lookahead (?=…)/(?!…) and lookbehind (?<=…)/(?<!…), each length-bounded and capture-free (variable-width lookbehind such as (?<=a|bb) is accepted, beyond re/PCRE's fixed-width limit). Unicode property classes \p{…} (General_Category and Script) match natively and linearly — a superset of re. Unsupported syntax — backreferences, atomic/possessive groups, conditional groups — is rejected with real::regex_error, never a silent divergence.

Matching is UTF-8 code-point-aware: classes and . accept non-ASCII ([é], [à-ÿ]), \w \d \s \b and IGNORECASE are Unicode in text mode (ASCII under flags::ascii / re.A), and no match boundary splits a character. The full Unicode model, the code-point-mode migration notes, and every intentional divergence from re (e.g. nullable-loop empty captures) are in docs/COMPATIBILITY.md.

C++ API

#include <real/real.hpp>
 
real::regex rx("hello");     // runtime pattern, storage sized exactly once
rx.match("hello world");     // anchored at the start   (Python re.match)
rx.fullmatch("hello");       // whole text              (Python re.fullmatch)
rx.search("say hello");      // leftmost match anywhere (Python re.search)

match/fullmatch/search return a real::match_result: matched(), operator bool, start(g), end(g), m[g] (a std::string_view into the searched text, which must outlive the result), and the same accessors by group name (m["year"], group_index).

for (auto& m : rx.find_iter(text)) { … }      // lazy, Python finditer rules
rx.find_all(text);                            // eager vector<match_result>
rx.replace(text, "$2:$1");                    // $&, $1…, ${name}, $$ — re.sub
rx.replace(text, "#", 2);                     // count limit
rx.split(text);                               // Python re.split, with groups

Empty matches follow Python's rules: they are yielded (even right after a non-empty match) and the scan then advances one whole codepoint. find_iter/find_all cannot be called on a temporary regex, and match/search/split cannot take a temporary std::string.

Drop-in for std::regex

Already using <regex>? real::compat is a drop-in for the <regex> surface on the char path — swap the include and alias the namespace, and your code keeps compiling:

#include <real/std/regex.hpp>   // was: #include <regex>
namespace re = real::compat;    // then re::regex / re::smatch / re::regex_search / …

It runs your pattern on REAL — linear-time, ReDoS-safe — wherever that is provably identical to std::regex, and falls back to std::regex everywhere else: behave identically, never a silent divergence. See the migration tour and the full docs/COMPATIBILITY.md.

Three memory modes

// Static: pattern compiled at compile time into exactly-sized constexpr
// arrays; an invalid pattern is a *compile error*.
constexpr real::static_regex<"(\\d{4})-(\\d{2})"> date;
static_assert(date.search("on 2026-06-10")[1] == "2026");  // constexpr match
 
// Hybrid: compile-time pattern, runtime text — matching performs zero heap
// allocations (state lives on the stack).
date.search(runtime_text);
 
// Dynamic: everything at runtime; the program is sized exactly once at
// compilation, match state is per-run scratch.
real::regex rx2(user_pattern, real::flags::icase);

DFA over a rule set (opt-in)

#include <real/dfa.hpp>   // opt-in: not pulled in by <real/real.hpp>
 
const std::array patterns {real::regex("\\s+"), real::regex("[0-9]+"),
                           real::regex("[A-Za-z_][A-Za-z0-9_]*")};
real::dfa d(std::span<const real::regex>(patterns));   // built once, then immutable
auto hit = d.match("foo");   // -> {rule_index = 2, length = 3}; std::nullopt if none

real::dfa fuses a set of patterns into one capture-free, maximal-munch DFA: a single left-to-right pass recognizes the winning rule (longest match; ties to the earliest pattern; empty excluded) instead of running each pattern in turn — linear-time and ReDoS-safe like the engine, built at run time and then immutable. It is the accelerated rule dispatch a lexer wants (SciLex's dfa_modes is built on it). A pattern carrying a zero-width assertion no DFA can represent ($, \b, multiline ^/$) throws real::dfa_error; lazy and greedy accept the same language, so feed it longest-match-faithful rules.

Python binding

An re-compatible module backed by the C++ engine (CPython Limited API, one abi3 extension, zero dependencies):

import real
 
real.search(r"(?P<y>\d{4})-(?P<m>\d{2})", "on 2026-06-10").groupdict()
real.compile(r"\w+").findall(text)         # findall/finditer/split/sub/subn
real.sub(r"\s+", " ", text)                # templates: \1, \g<name>, callables
real.search(r"(\w+)=(\w+)", "k=v").expand(r"\2:\1")   # Match.expand -> "v:k"
real.compile(rb"[^;]+").findall(raw)       # bytes patterns: raw-byte semantics

str matching is UTF-8 with character indices in start/end/span; bytes patterns get re's exact raw-byte semantics. Unsupported re features raise real.error at compile time. Build with make python-build && make python-test.

pip install real-regex installs one cp310-abi3 wheel per platform (CPython 3.10+; the self-contained sdist compiles where no wheel matches).

Embedding the C++ library through the Python package

The wheel also ships the C++ headers, so a project can compile against REAL located through its Python install — the convention used by petsc4py and slepc4py:

c++ -std=c++20 $(python -c "import real; print(real.get_include())") app.cpp

real.get_config() returns the version, the include directory and the required C++ standard.

Releasing. Run make release. It computes the next calendar version YYYY.M.PATCH — the patch resets each month, the first release of a month is .0 (PEP 440 drops leading zeros, so 2026.6.1, never 2026.06.001) — bumps it in pyproject.toml and bindings/python/real/__init__.py, then commits, tags and pushes. The tag drives release.yml, which checks the tag matches the version, builds abi3 wheels (cibuildwheel, Linux/macOS/Windows) and the sdist, and publishes to PyPI via Trusted Publishing (OIDC, no stored secret). The pushed tag is the single thing that triggers a publish.

Development

make help        # list all targets
make test        # build and run the test suite
make coverage    # line coverage report (LLVM)
make sanitize    # tests under ASan + UBSan
make lint        # clang-tidy
make misra       # MISRA C++:2023-oriented analysis
make fuzz        # libFuzzer robustness fuzzing (clang)
make doc         # API reference (Doxygen)
make format      # Uncrustify, in place
make format-check  # Uncrustify, dry-run; exits non-zero on diff

The API reference is published at https://reche23.github.io/real-regex/.

Select the compiler with make test CXX=g++-14. Every behaviour is tested at runtime and in constexpr (static_assert) under Clang and GCC; an equivalence suite checks the prefilter and fast paths never change results; a parity suite and a randomized differential fuzzer compare Python outputs against re.

Coverage bar. REAL holds a high line-coverage bar (mid-90s on include/), checked with make coverage. It deliberately does not adopt the 100%-on-all-four-dimensions (lines, functions, regions, and branches) gate used by the SciLang-stack libraries built on top of it: as the oldest and most complex engine here, its dual runtime/constexpr execution and Pike-VM branch structure leave some regions and branches impractical to drive to 100% without contrived tests. That lower-but-still-high bar is a deliberate, documented exception, not an oversight — REAL keeps its own gate (above) and its broad public CI.

CI exercises:

Platform	Architecture	Compiler
Linux	x86-64	GCC, Clang
Linux	AArch64	GCC
macOS	Apple Silicon (arm64)	Apple Clang
Windows	x86-64	MSVC

IntelLLVM (icpx), x86-64 macOS and the BSDs share the Clang flag set and are supported by the build configuration but not exercised in CI.

License

MIT — Copyright (c) 2026 René Chenard

Author

René Chenard