Metadata-Version: 2.4
Name: real-regex
Version: 2026.6.6
Summary: REAL — linear-time (ReDoS-safe) regex engine with an re-compatible API
Author-email: René Chenard <rene.chenard.1@ulaval.ca>
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

**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. Deferred (and rejected): 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`](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

```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);
```

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:

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

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

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
