Ah, I forgot to add https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88947 to the changelog.
I've modified the commit message locally. Thanks, Tamar > -----Original Message----- > From: Tamar Christina <[email protected]> > Sent: 29 July 2026 15:35 > To: [email protected] > Cc: nd <[email protected]>; [email protected]; [email protected]; > [email protected]; [email protected] > Subject: [patch v2 3/4][libstdc++]: Reject impossible regex DFS starts early > [PR126274] > > 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 previous patch in series: > > at -O2: > > email: +2.4% > URI: +3.6% > IPv4 +43.9% > > at -O3: > > email: +0.1%, > URI: +1.4% > IPv4: +42.7% > > Bootstrapped Regtested on aarch64-none-linux-gnu, > arm-none-linux-gnueabihf, x86_64-pc-linux-gnu > -m32, -m64 and no issues. > > Ok for master? > > 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 > a11410f0762441aeeaa32778c1d4676c92020e19..023f62e8a89d5f493228 > 64ab286d743f8f3cb7ed 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); > } > > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++- > v3/include/bits/regex_executor.tcc > index > 6f885321a69d685d7085e89653a02177c8b251a6..b1a87da5afee4d854708 > 207906d119f4b5b151b4 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: > > > --
