[patch 3/4][libstdc++]: Reject impossible regex DFS starts early [PR126274]

[Jonathan Wakely]

On Thu, 16 Jul 2026 at 19:01, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>
>
>
> On Thu, 16 Jul 2026, 15:31 Tamar Christina, <tamar.christina@arm.com> wrote:
>>
>> This patch add a conservative first-character precheck for DFS prefix search.
>> regex_search and regex_token_iterator try the pattern at each possible input
>> position. However for many regexp some of those positions can be rejected by
>> looking through the front (without consuming state) before building th full
>> DFS state which can be expensive to build only to realize that nothing matches.
>>
>> The pre-check only returns false when every inspected path reaches a first
>> consuming match state that rejects *_M_current, or reaches a dead end.  It
>> returns true for unsupported or context-sensitive states such as backrefs
>> and lookahead, so true means "run the normal executor" and false means
>> "this start position cannot match".
>>
>> This mainly helps IPv4-style scans where most positions are non-digits and
>> only a few positions can start a match.
>>
>> Benchmarks improvements compared to GCC 16:
>>   email: 55.5%
>>   URI:   55.2%
>>   IPv4:  68.0%
>>
>> Bootstrapped Regtested on aarch64-none-linux-gnu,
>> arm-none-linux-gnueabihf, x86_64-pc-linux-gnu
>> -m32, -m64 and no issues.
>>
>> Ok for master?
>
>
> Nice, there's a bugzilla somewhere that says we should do this.

This one: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88947

>
> This one is independent of the first two patches in the series, right?
>