real-regex 2026.6.19

REAL — linear-time (ReDoS-safe) regex engine with an re-compatible API

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	PCRE2-JIT	Python re
Linear-time, ReDoS-safe	✅	❌	✅	❌	❌
Lookarounds	✅	✅	❌	✅	✅
Header-only, zero-dependency	✅	✅¹	❌	❌	—
Constexpr (compile-time match)	✅	❌	❌	❌	❌
Drop-in Python re	✅²	❌	❌	❌	✅
Raw throughput	fast	slow	≈ REAL	fastest	slow

¹ part of the C++ standard library. ² for the supported subset (no backreferences, etc.). Throughput is qualitative — exact multipliers and methodology are in 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. vs CTRE (the other constexpr C++ regex): both are compile-time and header-only, but REAL is linear-time / ReDoS-safe where CTRE backtracks.

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	5.9 ms — linear
RE2	N = 100 000	0.2 ms — linear
std::regex	N = 22	refused — "complexity … exceeded a pre-set level"
Python re	n = 24	1118 ms — and climbing exponentially

REAL and RE2 stay linear; the backtracking engines refuse or blow up at trivially small inputs. These figures are from 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 & benchmarks

• API reference (Doxygen, with embedded coverage): https://reche23.github.io/real-regex/
• Benchmarks — a measured baseline with the exact machine and engine versions: BENCHMARKS.md

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

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 (members must be ASCII); [^…] matches any codepoint outside the set
\d \D \w \W \s \S	digit / word / space classes (ASCII sets, like Python's re.ASCII)
\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 (ASCII word characters)
\< \>	start / end of word (REAL extension, not in Python re)
(?imsx) prefix	global flags: i case-insensitive (ASCII), m multiline, s dotall, x verbose (ignore unescaped whitespace and # comments outside classes) — also real::flags on the constructor

Bounded lookarounds match in linear time: lookahead (?=...)/(?!...) and lookbehind (?<=...)/(?<!...). Each sub-pattern must be length-bounded (an unbounded sub such as (?=a*) is rejected) and is capture-free — groups inside a lookaround do not participate in the result, a deliberate divergence from re. Lookbehind accepts any bounded sub-pattern, including variable-width alternations such as (?<=a|bb), which re and PCRE reject as non-fixed-width. static_regex does not accept lookarounds yet.

Unsupported syntax is rejected with real::regex_error rather than silently diverging. Not yet: backreferences, atomic/possessive groups, Unicode property classes, Unicode case folding.

Unicode model: matching is UTF-8 byte-based, but every construct consumes whole codepoints (multi-byte sequences compile to byte-level alternatives), so match boundaries never split a character. Class members and the \d \w \s sets are ASCII by design; [^…], \D \W \S and . do match non-ASCII codepoints.

Divergence from Python: when a nullable loop body ends with an empty iteration — e.g. (a*)* on "aa" — Python captures that final empty iteration (''); REAL, like Perl/PCRE, keeps the last non-empty one ("aa"). Group 0 is identical either way.

Matching is linear in the input length: a Thompson NFA simulation (Pike VM) with marked states, so a pattern such as (a+)+b cannot trigger exponential backtracking. A literal prefilter and several whole-pattern fast paths (literals, fixed-width sequences, ./negated-class runs, alternations of straight-line branches) keep the constant factor low without leaving the linear-time guarantee.

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.

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 && 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 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