On Thu, 16 Jul 2026, 15:31 Tamar Christina, <[email protected]> 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 is independent of the first two patches in the series, right?
> Thanks,
> Tamar
>
> libstdc++-v3/ChangeLog:
>
> PR libstdc++/126274
> * include/bits/regex_executor.h (_M_search_from_first): Avoid
> needless
> recursions.
> (_M_maybe_start_match): New.
> * include/bits/regex_executor.tcc (_M_maybe_start_match): New.
>
> ---
> diff --git a/libstdc++-v3/include/bits/regex_executor.h
> b/libstdc++-v3/include/bits/regex_executor.h
> index
> 0a63b9b83789a700de63081ee61a7857028548e0..28dac152b6241ee44fd120528b9d1ebdbdf1aafa
> 100644
> --- a/libstdc++-v3/include/bits/regex_executor.h
> +++ b/libstdc++-v3/include/bits/regex_executor.h
> @@ -112,6 +112,28 @@ namespace __detail
> _M_search_from_first()
> {
> _M_current = _M_begin;
> + // Fast reject for DFS prefix search. regex_search and
> + // regex_token_iterator try the pattern at each possible starting
> + // position. If the regex can only start with a digit, running
> the full
> + // DFS executor at a space, letter, or punctuation character only
> builds
> + // frames to discover the first match state rejects that character.
> + //
> + // Example: for the IPv4 pattern
> + // (?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}...
> + // a current input character of 'x' cannot match any first
> consuming
> + // state. _M_maybe_start_match returns false and this starting
> position
> + // is skipped. At '2' it returns true, because at least one branch
> + // might match, so the normal executor still decides the complete
> + // result.
> + //
> + // This is intentionally disabled for backreferences. Pruning the
> + // search space for DFS reduces the number of frames we build and
> the
> + // time to find an actual match.
> + if (_M_search_mode == _Search_mode::_DFS
> + && !_M_nfa._M_has_backref
> + && _M_current != _M_end
> + && !_M_maybe_start_match(_M_start, 0))
> + return false;
> return _M_main(_Match_mode::_Prefix);
> }
>
> @@ -181,6 +203,9 @@ namespace __detail
> bool
> _M_main_dfs(_Match_mode __match_mode);
>
> + bool
> + _M_maybe_start_match(_StateIdT, size_t);
> +
> bool
> _M_main_bfs(_Match_mode __match_mode);
>
> diff --git a/libstdc++-v3/include/bits/regex_executor.tcc
> b/libstdc++-v3/include/bits/regex_executor.tcc
> index
> bf0594912688e0014a5928b6c6d600af6f80b31a..3a3bad8ecac485d452970c0aa26e6db34cabd1e5
> 100644
> --- a/libstdc++-v3/include/bits/regex_executor.tcc
> +++ b/libstdc++-v3/include/bits/regex_executor.tcc
> @@ -169,6 +169,101 @@ namespace __detail
> return _M_has_sol;
> }
>
> + // Return whether a prefix search at _M_current might still match after
> + // looking only through the non-consuming front of the NFA.
> + //
> + // This is not a general implementation. It is deliberately small and
> + // conservative: when it reaches a construct whose first consuming
> character
> + // is hard to know cheaply, it returns true and lets the normal
> executor run.
> + // The important fast paths are the common negative cases.
> + //
> + // Examples:
> + // * Pattern "[0-9]+" at input 'x': the first _S_opcode_match rejects
> 'x',
> + // so a full DFS search would only allocate/pop frames to fail.
> Return
> + // false and let regex_search advance the starting position.
> + //
> + // * Pattern "[01]?[0-9]" at input '9': the optional [01] branch
> rejects,
> + // but the skip branch can consume '9'. Return true and let DFS
> decide
> + // the full match.
> + //
> + // * Pattern "foo|bar" at input 'b': one alternative rejects, the other
> can
> + // start with 'b'. Return true.
> + template<typename _BiIter, typename _Alloc, typename _TraitsT>
> + bool _Executor<_BiIter, _Alloc, _TraitsT>::
> + _M_maybe_start_match(_StateIdT __i, size_t __depth)
> + {
> + // Depth is bounded by the NFA size so epsilon cycles cannot make
> the
> + // precheck recurse forever. Hitting the bound means "unknown", not
> + // "no match", so stay conservative and run the real executor.
> This is
> + // important for patterns such as "(a*)*" where epsilon paths can
> cycle
> + // before a consuming state is reached.
> + if (__depth > _M_nfa.size())
> + return true;
> +
> + // An invalid edge is a real dead end for the explored path.
> + if (__i == _S_invalid_state_id)
> + return false;
> +
> + const auto& __state = _M_nfa[__i];
> + switch (__state._M_opcode())
> + {
> + case _S_opcode_match:
> + return __state._M_matches(*_M_current);
> +
> + case _S_opcode_accept:
> + // Empty matches are possible, so the full executor must decide.
> + return true;
> +
> + case _S_opcode_subexpr_begin:
> + case _S_opcode_subexpr_end:
> + case _S_opcode_dummy:
> + // Captures and dummy states do not consume input, so they cannot
> + // affect the first-character decision. Continue along the only
> + // successor.
> + return _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> + case _S_opcode_line_begin_assertion:
> + // Assertions do not consume characters, but they can reject the
> + // current position. For "^abc" at a non-begin position, there
> is no
> + // need to run DFS merely to discover that ^ fails.
> + return _M_at_begin()
> + && _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> + case _S_opcode_line_end_assertion:
> + // Same idea for "$": if the assertion does not hold here, this
> + // starting position cannot match via this path.
> + return _M_at_end()
> + && _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> + case _S_opcode_word_boundary:
> + // Word-boundary assertions are also checked before the first
> + // consuming state. For "\bfoo" in the middle of "xfoo", this
> path
> + // rejects before testing 'f'.
> + return _M_word_boundary() == !__state._M_neg
> + && _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> + case _S_opcode_alternative:
> + // A branch might match if either arm can start with *_M_current.
> + // Example: "foo|bar" at 'b' rejects the "foo" arm but keeps the
> + // search because the "bar" arm is viable.
> + return _M_maybe_start_match(__state._M_alt, __depth + 1)
> + || _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> + case _S_opcode_repeat:
> + // Repeats can either enter the body or skip to the exit, so
> inspect
> + // both paths. This matters for constructs such as
> "[01]?[0-9]": at
> + // '9' the optional first digit can be skipped, while at 'x' both
> + // paths reject.
> + return _M_maybe_start_match(__state._M_alt, __depth + 1)
> + || _M_maybe_start_match(__state._M_next, __depth + 1);
> +
> + case _S_opcode_backref:
> + case _S_opcode_subexpr_lookahead:
> + default:
> + return true;
> + }
> + }
> +
> // ------------------------------------------------------------
> //
> // BFS mode:
>
>
> --
>
