Metadata-Version: 2.4
Name: real-regex
Version: 2026.6.20
Summary: REAL — linear-time (ReDoS-safe) regex engine with an re-compatible API
Author: René Chenard
License-Expression: MIT
Project-URL: Homepage, https://github.com/RECHE23/real-regex
Project-URL: Repository, https://github.com/RECHE23/real-regex
Project-URL: Documentation, https://reche23.github.io/real-regex/
Project-URL: Issues, https://github.com/RECHE23/real-regex/issues
Keywords: regex,regular-expression,redos,linear-time,re
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: C++
Classifier: Topic :: Text Processing
Classifier: Topic :: Software Development :: Libraries
Classifier: Operating System :: OS Independent
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# REAL

[![CI](https://github.com/RECHE23/real-regex/actions/workflows/ci.yml/badge.svg)](https://github.com/RECHE23/real-regex/actions/workflows/ci.yml)
[![PyPI](https://img.shields.io/pypi/v/real-regex)](https://pypi.org/project/real-regex/)
[![release](https://img.shields.io/github/v/release/RECHE23/real-regex)](https://github.com/RECHE23/real-regex/releases)
[![C++20](https://img.shields.io/badge/C%2B%2B-20-blue)](https://en.cppreference.com/w/cpp/20)
![header-only](https://img.shields.io/badge/header--only-yes-green)
[![coverage](https://img.shields.io/badge/coverage-%E2%89%A595%25-brightgreen)](https://reche23.github.io/real-regex/)
[![license](https://img.shields.io/badge/license-MIT-blue)](https://github.com/RECHE23/real-regex/blob/main/LICENSE)

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`](https://github.com/RECHE23/real-regex/blob/main/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 | **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](https://github.com/RECHE23/real-regex/blob/main/BENCHMARKS.md); 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:

```python
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:

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

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

More runnable programs — including the ReDoS demo — are in [`examples/`](https://github.com/RECHE23/real-regex/tree/main/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`](https://github.com/RECHE23/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++:

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

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

```sh
# 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](https://github.com/RECHE23/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](https://github.com/RECHE23/homebrew-sci) 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`](https://github.com/RECHE23/real-regex/blob/main/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

```cpp
#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`).

```cpp
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

```cpp
// 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)

```cpp
#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):

```python
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`:

```bash
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

```bash
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
