v2026.7.25

All five POSIX grammars now run on REAL's linear engine, the std::regex drop-in gains a per-operation
ReDoS-safety guarantee worded to hold, and a committed Fowler/AT&T conformance gate pins it — plus two
shipped bugs the measurement caught before this tag.

basic (BRE), awk, grep, and egrep join extended (shipped in 2026.7.24): a translatable pattern in
any of the five POSIX grammars is translated to REAL and run on the linear engine with leftmost-longest
(POSIX) bounds, instead of delegating to std::regex's backtracker. regex.posix_longest() reports it.

Each grammar's shape is honoured. BRE: \(/\) group and \{n\} quantify, while bare ( ) { } | + ? are
literals. awk: the C-escapes, where \b is backspace (0x08), not a word boundary — plus \n\t\r\f\v\a,
\/, \", and octal \ddd. grep (BRE) and egrep (ERE) read a newline as a top-level alternation of the
lines — which finally gives the BRE family a leftmost-longest acid it cannot otherwise express. A construct
only the backtracker runs — a backreference, an ECMAScript-ism, or a corner that is undefined in POSIX and
divergent across the std libraries (a medial ^/$, \]/\} outside a class, an empty alternation
branch) — declines to std::regex, never a silent wrong match.

The guarantee is worded to the one claim that cannot be gamed:

No accepted pattern can make matching super-linear — across all five POSIX grammars. Under the default
policy::strict, every accepted pattern executes each regex_search / regex_match in time linear in the
input. A pattern the linear engine cannot represent is rejected, never silently made non-linear;
policy::fallback delegates it to std::regex (forfeiting the guarantee).

regex_replace and the iterators compose up to O(n) such operations, so their worst-case total is
quadratic — inherent to repeated scanning on any linear engine (RE2 and the Rust regex crate
included), not a REAL limitation — but never exponential when running on REAL. A nullable pattern's
replace/iteration delegates to std::regex (correct results, not ReDoS-safe).

So (a+)+b under an egrep grammar runs regex_search in microseconds where a std::regex drop-in blows
up exponentially. The quadratic-iteration cost is self-disclosed, so the claim has no gotcha left.

The three vendored testregex corpora (basic / nullsubexpr / repetition) run through real::compat vs the
local std::regex as a gate step, arbitrated three ways — REAL, std, and the corpus's own POSIX-longest
expectation. 403 cases are perfect (REAL == std == Fowler); the hard invariants (REAL agrees with std on
every routed case, never over-accepts, the perfect count, and the per-file parsed-case counts — a
"no silent caps" pin) are enforced on both libc++ and libstdc++. It carries a reference AT&T decoder (the
i flag, the SAME directive, NULL/NIL, \xHH and octal escapes) that replaces a lossy shared parse.

• A leading ] in a POSIX bracket expression ([]], [^]b]) is a literal member — it was emitted as a
  bare ], which REAL reads as an empty class, so the pattern never matched. Shipped for extended in
  2026.7.24; the conformance gate's "REAL alone diverges" bucket caught it before this tag.
• An empty alternation branch ((|a)*, ab|) is rejected by std::regex in the POSIX grammars, but was
  translated and routed to REAL — so compat over-accepted vs its own std. It now declines, staying ≡ std.