real-regex 2026.6.11

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

REAL

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.

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

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.

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. A measured baseline, with the exact machine and engine versions, is archived in BENCHMARKS.md.

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

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.

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.

The pure library is standard C++20 with no platform dependencies. real::real is the CMake target, available three ways — add_subdirectory, FetchContent, or an installed config package:

# After `cmake --install <build> --prefix <prefix>`:
find_package(real CONFIG REQUIRED)
target_link_libraries(app PRIVATE real::real)

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