> -----Original Message-----
> From: Jonathan Wakely <[email protected]>
> Sent: 29 July 2026 16:47
> To: Tamar Christina <[email protected]>
> Cc: [email protected]; nd <[email protected]>; [email protected];
> [email protected]; [email protected]
> Subject: Re: [patch v2 1/4][libstdc++]: Continue with regex DFS traversals
> without next frames [PR126274]
>
> On Wed, 29 Jul 2026 at 16:44 +0100, Jonathan Wakely wrote:
> >On Wed, 29 Jul 2026 at 15:34 +0100, Tamar Christina wrote:
> >>The change in r16-7193-g158ad5f96954da5fa24d5c2a91ae92417fb62e20
> changed
> >>the recursive implementation with an iterative one using an explicit heap.
> >>
> >>However one benefit of the previous implementation is that the frame did
> >>not have to be saved and popped when the match is supposed to continue.
> >>
> >>This means that on hot paths we now have additional memory accesses and
> >>need additional instructions to calculate the memref addresses.
> >>
> >>For DFS matching this is clearly suboptimal since when _M_rep_once_more
> >>then we push and pop the same state but there is enough other acceses
> >>in between the push and pop that we get a lot of cache misses.
> >>
> >>This makes all the private _m_handle_* methods return a _StateIdT which
> allows
> >>the caller to deal with the value, so that for DFS we can avoid pushing the
> >>frame if needed.
> >>
> >>For DFS we try to consume the state immediately until we're told to
> >>stop.
> >>
> >>For this to work the methods have to me marked always inline, because a
> key part
> >>of the optimization is to keep the values in registers rather than passing
> >>through stack and the function call overheads and AAPCS requirements
> would
> >>negate the benefits.
> >>
> >>The patch also reserves some frames in the initial vector to avoid having
> >>resizes on the hot path. To avoid large RSS before matching even starts
> >>we provide a cap to the initial reservations. However I have not yet
> addressed
> >>
> >>Jakub's comment that the cap at 255 is likely to big. I need to do more
> >>experiments here to figure out if it's even needed. For now I left it
> >>since I
> >>am expecting another respin here.
> >>
> >>The __dfs_mode changes are because the constexpr patch still gave a big
> boost so
> >>it prepares to apply it.
> >>
> >>There is still a regression until the end of the series and each patch
> >>will chip away at it.
> >>
> >>Also note that with none of these changes do I see an increase heap or stack
> >>usage that the original fix fixed. RSS stays about the same.
> >>
> >>PS. thanks for the link to the algorithm in the source, it was useful to
> >>understand how the machinery works!
> >>
> >>Benchmark improvements vs GCC 16:
> >>
> >>at -O2:
> >>
> >> email: +36.1%
> >> URI: +36.5%
> >> IPv4 +33.0%
> >>
> >>at -O3:
> >>
> >> email: +45.5%,
> >> URI: +44.9%
> >> IPv4: +43.0%
> >>
> >>On Neoverse-V1
> >>
> >>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 (_Executor): Reserve frame space.
> >> (_M_rep_once_more, _M_handle_repeat, _M_handle_subexpr_begin,
> >> _M_handle_subexpr_end, _M_handle_line_begin_assertion,
> >> _M_handle_line_end_assertion, _M_handle_word_boundary,
> >> _M_handle_subexpr_lookahead, _M_handle_match,
> _M_handle_backref,
> >> _M_node): return StateIdT.
> >> (_M_visited): Mark inline.
> >> * include/bits/regex_executor.tcc (_M_rep_once_more,
> _M_handle_repeat,
> >> _M_handle_subexpr_begin, _M_handle_subexpr_end,
> >> _M_handle_line_begin_assertion, _M_handle_line_end_assertion,
> >> _M_handle_word_boundary, _M_handle_subexpr_lookahead,
> _M_handle_match,
> >> _M_handle_backref): Return state, mark always inline.
> >> (_M_node): Return StateIdT and also decide what to do with the value
> >> after return.
> >> (_M_dfs): Traverse states iteratively for _S_fopcode_next,
> >> _S_fopcode_fallback_next, _S_fopcode_fallback_rep_once_more
> >> and _S_fopcode_rep_once_more.
> >>
> >>---
> >>diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-
> v3/include/bits/regex_executor.h
> >>index
> 797ad702784b6d1bf07734d91683946d989630f5..23fe828078a32194d99
> 6aeb3bfc37e2c46513c41 100644
> >>--- a/libstdc++-v3/include/bits/regex_executor.h
> >>+++ b/libstdc++-v3/include/bits/regex_executor.h
> >>@@ -86,6 +86,11 @@ namespace __detail
> >> using namespace regex_constants;
> >> if (__flags & match_prev_avail) // ignore not_bol and not_bow
> >> _M_flags &= ~(match_not_bol | match_not_bow);
> >>+ // Reserve NFA sized frames up front to prevent having to constantly
> >>+ // reallocate frames. To avoid an explosion in state with large regexp
> >>+ // before any matching is ever done limit the reservation to 256.
> >>+ // This should cover a large class of regexp.
> >>+ _M_frames.reserve(std::min<size_t>(_M_nfa.size(), 256));
> >> if (_M_search_mode == _Search_mode::_BFS)
> >> _M_visited_states = new bool[_M_nfa.size()];
> >> }
> >>@@ -113,43 +118,43 @@ namespace __detail
> >> _M_search();
> >>
> >> private:
> >>- void
> >>+ _StateIdT
> >> _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_repeat(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_subexpr_begin(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_subexpr_end(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_line_begin_assertion(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_line_end_assertion(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_word_boundary(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_match(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_backref(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_accept(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_alternative(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_node(_Match_mode, _StateIdT);
> >>
> >> void
> >>@@ -247,7 +252,7 @@ namespace __detail
> >> return (_M_re._M_automaton->_M_options() & __m) == __m;
> >> }
> >>
> >>- bool
> >>+ inline bool
> >> _M_visited(_StateIdT __i)
> >> {
> >> if (_M_visited_states)
> >>diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-
> v3/include/bits/regex_executor.tcc
> >>index
> 167a7a345300868ed5e0852e328569aec47e3d0d..ed53df63a5a304f1db04
> c3519b986f0e5750e3f5 100644
> >>--- a/libstdc++-v3/include/bits/regex_executor.tcc
> >>+++ b/libstdc++-v3/include/bits/regex_executor.tcc
> >>@@ -250,8 +250,14 @@ namespace __detail
> >> // infinite loop by refusing to continue when it's already been
> >> // visited more than twice. It's `twice` instead of `once` because
> >> // we need to spare one more time for potential group capture.
> >>+ //
> >>+ // If the node cannot be re-entered anymore from the current state then
> return
> >>+ // _S_invalid_state_id otherwise return the current state without going
> >>+ // through a vector, allowing the caller to decide what to do with the
> >>state
> >>+ // This is beneficial for DFS since DFS can continue with the next state
> >>+ // immediately
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_rep_once_more(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >>@@ -263,7 +269,7 @@ namespace __detail
> >> _M_frames.back()._M_count = __rep_count.second;
> >> __rep_count.first = _M_current;
> >> __rep_count.second = 1;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >>+ return __state._M_alt;
> >> }
> >> else
> >> {
> >>@@ -271,9 +277,10 @@ namespace __detail
> >> {
> >> __rep_count.second++;
> >> _M_frames.emplace_back(_S_fopcode_decrement_rep_count,
> __i);
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >>+ return __state._M_alt;
> >> }
> >> }
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> // _M_alt branch is "match once more", while _M_next is "get me out
> >>@@ -281,8 +288,11 @@ namespace __detail
> >> // mean the same thing, and we need to choose the correct order under
> >> // given greedy mode.
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>- _M_handle_repeat(_Match_mode, _StateIdT __i)
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ _M_handle_repeat(_Match_mode __match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> // Greedy.
> >>@@ -294,7 +304,7 @@ namespace __detail
> >> _M_current);
> >> else
> >> _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>- _M_frames.emplace_back(_S_fopcode_rep_once_more, __i);
> >>+ return _M_rep_once_more(__match_mode, __i);
> >> }
> >> else // Non-greedy mode
> >> {
> >>@@ -303,7 +313,7 @@ namespace __detail
> >> // vice-versa.
> >> _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> __i,
> >> _M_current);
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >> else
> >> {
> >>@@ -316,97 +326,122 @@ namespace __detail
> >> // accepted state *must* be better than a solution that
> >> // matches a non-greedy quantifier one more time.
> >>
> _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i);
> >>- _M_frames.emplace_back(_S_fopcode_next,
> __state._M_next);
> >>+ return __state._M_next;
> >> }
> >> }
> >> }
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_subexpr_begin(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> auto& __res = _M_cur_results[__state._M_subexpr];
> >>- _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >>- static_cast<_StateIdT>(__state._M_subexpr),
> >>- __res.first);
> >>+ if (_M_nfa._M_has_backref
> >>+ || __state._M_subexpr != 0
> >>+ || _M_search_mode != _Search_mode::_DFS)
> >>+ _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >>+ static_cast<_StateIdT>(__state._M_subexpr),
> >>+ __res.first);
> >> __res.first = _M_current;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_subexpr_end(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> auto& __res = _M_cur_results[__state._M_subexpr];
> >>- _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >>- static_cast<_StateIdT>(__state._M_subexpr),
> >>- __res.second);
> >>- _M_frames.back()._M_subexpr_end = true;
> >>- _M_frames.back()._M_matched = __res.matched;
> >>+ if (_M_nfa._M_has_backref
> >>+ || __state._M_subexpr != 0
> >>+ || _M_search_mode != _Search_mode::_DFS)
> >>+ {
> >>+ _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >>+ static_cast<_StateIdT>(__state._M_subexpr),
> >>+ __res.second);
> >>+ _M_frames.back()._M_subexpr_end = true;
> >>+ _M_frames.back()._M_matched = __res.matched;
> >>+ }
> >>+
> >> __res.second = _M_current;
> >> __res.matched = true;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_line_begin_assertion(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_at_begin())
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_line_end_assertion(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_at_end())
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_word_boundary(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_word_boundary() == !__state._M_neg)
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> // Here __state._M_alt offers a single start node for a sub-NFA.
> >> // We recursively invoke our algorithm to match the sub-NFA.
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_subexpr_lookahead(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_lookahead(__state._M_alt) == !__state._M_neg)
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_match(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_current == _M_end)
> >>- return;
> >>+ return _S_invalid_state_id;
> >> if (_M_search_mode == _Search_mode::_DFS)
> >> {
> >> if (__state._M_matches(*_M_current))
> >> {
> >> ++_M_current;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >> }
> >> else
> >> if (__state._M_matches(*_M_current))
> >> _M_match_queue.emplace_back(__state._M_next, _M_cur_results);
> >>+
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _TraitsT>
> >>@@ -462,7 +497,7 @@ namespace __detail
> >> // (_M_current, _M_current + (__submatch.second - __submatch.first)).
> >> // If matched, keep going; else just return and try another state.
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_backref(_Match_mode, _StateIdT __i)
> >> {
> >> __glibcxx_assert(_M_search_mode == _Search_mode::_DFS);
> >>@@ -470,7 +505,7 @@ namespace __detail
> >> const auto& __state = _M_nfa[__i];
> >> auto& __submatch = _M_cur_results[__state._M_backref_index];
> >> if (!__submatch.matched)
> >>- return;
> >>+ return _S_invalid_state_id;
> >> auto __last = _M_current;
> >> for (auto __tmp = __submatch.first;
> >> __last != _M_end && __tmp != __submatch.second;
> >>@@ -482,12 +517,17 @@ namespace __detail
> >> __submatch.first, __submatch.second, _M_current, __last))
> >> {
> >> _M_current = __last;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >>+
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_accept(_Match_mode __match_mode, _StateIdT)
> >> {
> >> if (_M_search_mode == _Search_mode::_DFS)
> >>@@ -528,7 +568,7 @@ namespace __detail
> >> {
> >> if (_M_current == _M_begin
> >> && (_M_flags & regex_constants::match_not_null))
> >>- return;
> >>+ return _S_invalid_state_id;
> >> if (__match_mode == _Match_mode::_Prefix || _M_current ==
> _M_end)
> >> if (!_M_has_sol)
> >> {
> >>@@ -536,10 +576,14 @@ namespace __detail
> >> _M_results = _M_cur_results;
> >> }
> >> }
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_alternative(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >>@@ -549,7 +593,7 @@ namespace __detail
> >> // Pick lhs if it matches. Only try rhs if it doesn't.
> >> _M_frames.emplace_back(_S_fopcode_fallback_next,
> __state._M_next,
> >> _M_current);
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >>+ return __state._M_alt;
> >> }
> >> else
> >> {
> >>@@ -557,7 +601,7 @@ namespace __detail
> >> // See "case _S_opcode_accept:" handling above.
> >> _M_frames.emplace_back(_S_fopcode_posix_alternative,
> __state._M_next,
> >> _M_current);
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >>+ return __state._M_alt;
> >> }
> >> }
> >>
> >>@@ -565,50 +609,63 @@ namespace __detail
> >>#ifdef __OPTIMIZE__
> >> [[__gnu__::__always_inline__]]
> >>#endif
> >>- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_node(_Match_mode __match_mode, _StateIdT __i)
> >> {
> >>- if (_M_visited(__i))
> >>- return;
> >>+ // DFS has no _M_visited implementation as such don't even have the
> branch
> >>+ // or the check in the call graph.
> >>+ if (_M_search_mode == _Search_mode::_BFS)
> >>+ if (_M_visited(__i))
> >>+ return _S_invalid_state_id;
> >>
> >>+ _StateIdT __next = _S_invalid_state_id;
> >> switch (_M_nfa[__i]._M_opcode())
> >> {
> >> case _S_opcode_repeat:
> >>- _M_handle_repeat(__match_mode, __i); break;
> >>+ __next = _M_handle_repeat(__match_mode, __i); break;
> >> case _S_opcode_subexpr_begin:
> >>- _M_handle_subexpr_begin(__match_mode, __i); break;
> >>+ __next = _M_handle_subexpr_begin(__match_mode, __i);
> >>+ break;
> >> case _S_opcode_subexpr_end:
> >>- _M_handle_subexpr_end(__match_mode, __i); break;
> >>+ __next = _M_handle_subexpr_end(__match_mode, __i);
> >>+ break;
> >> case _S_opcode_line_begin_assertion:
> >>- _M_handle_line_begin_assertion(__match_mode, __i); break;
> >>+ __next = _M_handle_line_begin_assertion(__match_mode, __i);
> break;
> >> case _S_opcode_line_end_assertion:
> >>- _M_handle_line_end_assertion(__match_mode, __i); break;
> >>+ __next = _M_handle_line_end_assertion(__match_mode, __i); break;
> >> case _S_opcode_word_boundary:
> >>- _M_handle_word_boundary(__match_mode, __i); break;
> >>+ __next = _M_handle_word_boundary(__match_mode, __i); break;
> >> case _S_opcode_subexpr_lookahead:
> >>- _M_handle_subexpr_lookahead(__match_mode, __i); break;
> >>+ __next = _M_handle_subexpr_lookahead(__match_mode, __i);
> break;
> >> case _S_opcode_match:
> >>- _M_handle_match(__match_mode, __i); break;
> >>+ __next = _M_handle_match(__match_mode, __i); break;
> >> case _S_opcode_backref:
> >> if (_M_search_mode == _Search_mode::_DFS)
> >>- _M_handle_backref(__match_mode, __i);
> >>+ __next = _M_handle_backref(__match_mode, __i);
> >> else
> >> __builtin_unreachable();
> >> break;
> >> case _S_opcode_accept:
> >>- _M_handle_accept(__match_mode, __i); break;
> >>+ __next = _M_handle_accept(__match_mode, __i); break;
> >> case _S_opcode_alternative:
> >>- _M_handle_alternative(__match_mode, __i); break;
> >>+ __next = _M_handle_alternative(__match_mode, __i); break;
> >> default:
> >> __glibcxx_assert(false);
> >> }
> >>+ if (_M_search_mode == _Search_mode::_BFS)
> >>+ {
> >>+ if (__next != _S_invalid_state_id)
> >>+ _M_frames.emplace_back(_S_fopcode_next, __next);
> >>+ return _S_invalid_state_id;
> >>+ }
> >>+ else
> >>+ return __next;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >> void _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_dfs(_Match_mode __match_mode, _StateIdT __start)
> >> {
> >>- const bool __dfs_mode = (_M_search_mode == _Search_mode::_DFS);
> >> _M_frames.emplace_back(_S_fopcode_next, __start);
> >>
> >> while (!_M_frames.empty())
> >>@@ -621,27 +678,49 @@ namespace __detail
> >> case _S_fopcode_fallback_next:
> >> if (_M_has_sol)
> >> break;
> >>- if (__dfs_mode)
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >> _M_current = __frame._M_pos;
> >> [[__fallthrough__]];
> >> case _S_fopcode_next:
> >>- _M_node(__match_mode, __frame._M_state_id);
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >>+ // Follow immediate successors without re-entering the frame
> >>+ // loop until we fail. This avoids the needless state save and
> >>+ // restore through memory.
> >>+ for (_StateIdT __next = __frame._M_state_id;
> >>+ __next != _S_invalid_state_id;)
> >>+ __next = _M_node(__match_mode, __next);
> >>+ else
> >>+ _M_node(__match_mode, __frame._M_state_id);
> >> break;
> >>
> >> case _S_fopcode_fallback_rep_once_more:
> >> if (_M_has_sol)
> >> break;
> >>- if (__dfs_mode)
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >> _M_current = __frame._M_pos;
> >> [[__fallthrough__]];
> >> case _S_fopcode_rep_once_more:
> >>- _M_rep_once_more(__match_mode, __frame._M_state_id);
> >>+ {
> >>+ _StateIdT __next
> >>+ = _M_rep_once_more(__match_mode,
> __frame._M_state_id);
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >>+ // _M_rep_once_more returned the repeated body's start
> state.
> >>+ // Continue directly in DFS; BFS must materialize the state as
> >>+ // a queue/frame item because it advances by input position
> >>+ // rather than by backtracking order. Splitting this in a
> >>+ // specialized path preserves the behavior for both but for
> >>+ // DFS it avoids the intermediate allocations.
> >>+ for (; __next != _S_invalid_state_id;)
> >>+ __next = _M_node(__match_mode, __next);
> >>+ else if (__next != _S_invalid_state_id)
> >>+ _M_frames.emplace_back(_S_fopcode_next, __next);
> >>+ }
> >> break;
> >>
> >> case _S_fopcode_posix_alternative:
> >> _M_frames.emplace_back(_S_fopcode_merge_sol, 0,
> _M_has_sol);
> >> _M_frames.emplace_back(_S_fopcode_next,
> __frame._M_state_id);
> >>- if (__dfs_mode)
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >> _M_current = __frame._M_pos;
> >> _M_has_sol = false;
> >> break;
> >>
> >>
> >>--
> >
> >>diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-
> v3/include/bits/regex_executor.h
> >>index
> 797ad702784b6d1bf07734d91683946d989630f5..23fe828078a32194d99
> 6aeb3bfc37e2c46513c41 100644
> >>--- a/libstdc++-v3/include/bits/regex_executor.h
> >>+++ b/libstdc++-v3/include/bits/regex_executor.h
> >>@@ -86,6 +86,11 @@ namespace __detail
> >> using namespace regex_constants;
> >> if (__flags & match_prev_avail) // ignore not_bol and not_bow
> >> _M_flags &= ~(match_not_bol | match_not_bow);
> >>+ // Reserve NFA sized frames up front to prevent having to constantly
> >>+ // reallocate frames. To avoid an explosion in state with large regexp
> >>+ // before any matching is ever done limit the reservation to 256.
> >>+ // This should cover a large class of regexp.
> >>+ _M_frames.reserve(std::min<size_t>(_M_nfa.size(), 256));
> >> if (_M_search_mode == _Search_mode::_BFS)
> >> _M_visited_states = new bool[_M_nfa.size()];
> >> }
> >>@@ -113,43 +118,43 @@ namespace __detail
> >> _M_search();
> >>
> >> private:
> >>- void
> >>+ _StateIdT
> >
> >These changes are an ABI break. The mangled name of these member
> >functions does not include the return type, so instantiations in
> >object files compiled with GCC 16.1 would not return anything. If a
> >caller compiled by GCC 17 links to the old instantiation, the caller
> >will try to use the return value, which will be uninitialized garbage
> >on the stack.
> >
> >Either the function names need to change, or their parameters need to
> >change, or they need an [[abi_tag("...")]] attribute. Some change to
> >cause them to mangle differently.
Hmm this is true. The changes were done in response to v1 to avoid duplicating
the logic but as you say it does change the ABI.
Is there any preference here?
>
> Making them templates (as in PATCH 2/4) does cause the mangled name to
> change. But PATCH 2/4 only makes that change to some of them,
> _M_rep_once_more is not changed to a template.
Yeah I was a bit conservative because Patrick wasn't quite fond of the
templates.
But happy to do whatever you folks say here :)
Thanks,
Tamar
>
> >> _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_repeat(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_subexpr_begin(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_subexpr_end(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_line_begin_assertion(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_line_end_assertion(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_word_boundary(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_subexpr_lookahead(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_match(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_backref(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_accept(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_handle_alternative(_Match_mode, _StateIdT);
> >>
> >>- void
> >>+ _StateIdT
> >> _M_node(_Match_mode, _StateIdT);
> >>
> >> void
> >>@@ -247,7 +252,7 @@ namespace __detail
> >> return (_M_re._M_automaton->_M_options() & __m) == __m;
> >> }
> >>
> >>- bool
> >>+ inline bool
> >
> >I don't think this does anything.
> >
> >> _M_visited(_StateIdT __i)
> >> {
> >> if (_M_visited_states)
> >>diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-
> v3/include/bits/regex_executor.tcc
> >>index
> 167a7a345300868ed5e0852e328569aec47e3d0d..ed53df63a5a304f1db04
> c3519b986f0e5750e3f5 100644
> >>--- a/libstdc++-v3/include/bits/regex_executor.tcc
> >>+++ b/libstdc++-v3/include/bits/regex_executor.tcc
> >>@@ -250,8 +250,14 @@ namespace __detail
> >> // infinite loop by refusing to continue when it's already been
> >> // visited more than twice. It's `twice` instead of `once` because
> >> // we need to spare one more time for potential group capture.
> >>+ //
> >>+ // If the node cannot be re-entered anymore from the current state then
> return
> >>+ // _S_invalid_state_id otherwise return the current state without going
> >>+ // through a vector, allowing the caller to decide what to do with the
> >>state
> >>+ // This is beneficial for DFS since DFS can continue with the next state
> >>+ // immediately
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_rep_once_more(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >>@@ -263,7 +269,7 @@ namespace __detail
> >> _M_frames.back()._M_count = __rep_count.second;
> >> __rep_count.first = _M_current;
> >> __rep_count.second = 1;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >>+ return __state._M_alt;
> >> }
> >> else
> >> {
> >>@@ -271,9 +277,10 @@ namespace __detail
> >> {
> >> __rep_count.second++;
> >> _M_frames.emplace_back(_S_fopcode_decrement_rep_count,
> __i);
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >>+ return __state._M_alt;
> >> }
> >> }
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> // _M_alt branch is "match once more", while _M_next is "get me out
> >>@@ -281,8 +288,11 @@ namespace __detail
> >> // mean the same thing, and we need to choose the correct order under
> >> // given greedy mode.
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>- _M_handle_repeat(_Match_mode, _StateIdT __i)
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ _M_handle_repeat(_Match_mode __match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> // Greedy.
> >>@@ -294,7 +304,7 @@ namespace __detail
> >> _M_current);
> >> else
> >> _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>- _M_frames.emplace_back(_S_fopcode_rep_once_more, __i);
> >>+ return _M_rep_once_more(__match_mode, __i);
> >> }
> >> else // Non-greedy mode
> >> {
> >>@@ -303,7 +313,7 @@ namespace __detail
> >> // vice-versa.
> >> _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more,
> __i,
> >> _M_current);
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >> else
> >> {
> >>@@ -316,97 +326,122 @@ namespace __detail
> >> // accepted state *must* be better than a solution that
> >> // matches a non-greedy quantifier one more time.
> >>
> _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i);
> >>- _M_frames.emplace_back(_S_fopcode_next,
> __state._M_next);
> >>+ return __state._M_next;
> >> }
> >> }
> >> }
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_subexpr_begin(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> auto& __res = _M_cur_results[__state._M_subexpr];
> >>- _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >>- static_cast<_StateIdT>(__state._M_subexpr),
> >>- __res.first);
> >>+ if (_M_nfa._M_has_backref
> >>+ || __state._M_subexpr != 0
> >>+ || _M_search_mode != _Search_mode::_DFS)
> >>+ _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >>+ static_cast<_StateIdT>(__state._M_subexpr),
> >>+ __res.first);
> >> __res.first = _M_current;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_subexpr_end(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> auto& __res = _M_cur_results[__state._M_subexpr];
> >>- _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >>- static_cast<_StateIdT>(__state._M_subexpr),
> >>- __res.second);
> >>- _M_frames.back()._M_subexpr_end = true;
> >>- _M_frames.back()._M_matched = __res.matched;
> >>+ if (_M_nfa._M_has_backref
> >>+ || __state._M_subexpr != 0
> >>+ || _M_search_mode != _Search_mode::_DFS)
> >>+ {
> >>+ _M_frames.emplace_back(_S_fopcode_restore_cur_results,
> >>+ static_cast<_StateIdT>(__state._M_subexpr),
> >>+ __res.second);
> >>+ _M_frames.back()._M_subexpr_end = true;
> >>+ _M_frames.back()._M_matched = __res.matched;
> >>+ }
> >>+
> >> __res.second = _M_current;
> >> __res.matched = true;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_line_begin_assertion(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_at_begin())
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_line_end_assertion(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_at_end())
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_word_boundary(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_word_boundary() == !__state._M_neg)
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> // Here __state._M_alt offers a single start node for a sub-NFA.
> >> // We recursively invoke our algorithm to match the sub-NFA.
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_subexpr_lookahead(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_lookahead(__state._M_alt) == !__state._M_neg)
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_match(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >> if (_M_current == _M_end)
> >>- return;
> >>+ return _S_invalid_state_id;
> >> if (_M_search_mode == _Search_mode::_DFS)
> >> {
> >> if (__state._M_matches(*_M_current))
> >> {
> >> ++_M_current;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >> }
> >> else
> >> if (__state._M_matches(*_M_current))
> >> _M_match_queue.emplace_back(__state._M_next, _M_cur_results);
> >>+
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _TraitsT>
> >>@@ -462,7 +497,7 @@ namespace __detail
> >> // (_M_current, _M_current + (__submatch.second - __submatch.first)).
> >> // If matched, keep going; else just return and try another state.
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_backref(_Match_mode, _StateIdT __i)
> >> {
> >> __glibcxx_assert(_M_search_mode == _Search_mode::_DFS);
> >>@@ -470,7 +505,7 @@ namespace __detail
> >> const auto& __state = _M_nfa[__i];
> >> auto& __submatch = _M_cur_results[__state._M_backref_index];
> >> if (!__submatch.matched)
> >>- return;
> >>+ return _S_invalid_state_id;
> >> auto __last = _M_current;
> >> for (auto __tmp = __submatch.first;
> >> __last != _M_end && __tmp != __submatch.second;
> >>@@ -482,12 +517,17 @@ namespace __detail
> >> __submatch.first, __submatch.second, _M_current, __last))
> >> {
> >> _M_current = __last;
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_next);
> >>+ return __state._M_next;
> >> }
> >>+
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_accept(_Match_mode __match_mode, _StateIdT)
> >> {
> >> if (_M_search_mode == _Search_mode::_DFS)
> >>@@ -528,7 +568,7 @@ namespace __detail
> >> {
> >> if (_M_current == _M_begin
> >> && (_M_flags & regex_constants::match_not_null))
> >>- return;
> >>+ return _S_invalid_state_id;
> >> if (__match_mode == _Match_mode::_Prefix || _M_current ==
> _M_end)
> >> if (!_M_has_sol)
> >> {
> >>@@ -536,10 +576,14 @@ namespace __detail
> >> _M_results = _M_cur_results;
> >> }
> >> }
> >>+ return _S_invalid_state_id;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >>- void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+#ifdef __OPTIMIZE__
> >>+ [[__gnu__::__always_inline__]]
> >>+#endif
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_handle_alternative(_Match_mode, _StateIdT __i)
> >> {
> >> const auto& __state = _M_nfa[__i];
> >>@@ -549,7 +593,7 @@ namespace __detail
> >> // Pick lhs if it matches. Only try rhs if it doesn't.
> >> _M_frames.emplace_back(_S_fopcode_fallback_next,
> __state._M_next,
> >> _M_current);
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >>+ return __state._M_alt;
> >> }
> >> else
> >> {
> >>@@ -557,7 +601,7 @@ namespace __detail
> >> // See "case _S_opcode_accept:" handling above.
> >> _M_frames.emplace_back(_S_fopcode_posix_alternative,
> __state._M_next,
> >> _M_current);
> >>- _M_frames.emplace_back(_S_fopcode_next, __state._M_alt);
> >>+ return __state._M_alt;
> >> }
> >> }
> >>
> >>@@ -565,50 +609,63 @@ namespace __detail
> >>#ifdef __OPTIMIZE__
> >> [[__gnu__::__always_inline__]]
> >>#endif
> >>- inline void _Executor<_BiIter, _Alloc, _TraitsT>::
> >>+ inline _StateIdT _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_node(_Match_mode __match_mode, _StateIdT __i)
> >> {
> >>- if (_M_visited(__i))
> >>- return;
> >>+ // DFS has no _M_visited implementation as such don't even have the
> branch
> >>+ // or the check in the call graph.
> >>+ if (_M_search_mode == _Search_mode::_BFS)
> >>+ if (_M_visited(__i))
> >>+ return _S_invalid_state_id;
> >>
> >>+ _StateIdT __next = _S_invalid_state_id;
> >> switch (_M_nfa[__i]._M_opcode())
> >> {
> >> case _S_opcode_repeat:
> >>- _M_handle_repeat(__match_mode, __i); break;
> >>+ __next = _M_handle_repeat(__match_mode, __i); break;
> >> case _S_opcode_subexpr_begin:
> >>- _M_handle_subexpr_begin(__match_mode, __i); break;
> >>+ __next = _M_handle_subexpr_begin(__match_mode, __i);
> >>+ break;
> >> case _S_opcode_subexpr_end:
> >>- _M_handle_subexpr_end(__match_mode, __i); break;
> >>+ __next = _M_handle_subexpr_end(__match_mode, __i);
> >>+ break;
> >> case _S_opcode_line_begin_assertion:
> >>- _M_handle_line_begin_assertion(__match_mode, __i); break;
> >>+ __next = _M_handle_line_begin_assertion(__match_mode, __i);
> break;
> >> case _S_opcode_line_end_assertion:
> >>- _M_handle_line_end_assertion(__match_mode, __i); break;
> >>+ __next = _M_handle_line_end_assertion(__match_mode, __i); break;
> >> case _S_opcode_word_boundary:
> >>- _M_handle_word_boundary(__match_mode, __i); break;
> >>+ __next = _M_handle_word_boundary(__match_mode, __i); break;
> >> case _S_opcode_subexpr_lookahead:
> >>- _M_handle_subexpr_lookahead(__match_mode, __i); break;
> >>+ __next = _M_handle_subexpr_lookahead(__match_mode, __i);
> break;
> >> case _S_opcode_match:
> >>- _M_handle_match(__match_mode, __i); break;
> >>+ __next = _M_handle_match(__match_mode, __i); break;
> >> case _S_opcode_backref:
> >> if (_M_search_mode == _Search_mode::_DFS)
> >>- _M_handle_backref(__match_mode, __i);
> >>+ __next = _M_handle_backref(__match_mode, __i);
> >> else
> >> __builtin_unreachable();
> >> break;
> >> case _S_opcode_accept:
> >>- _M_handle_accept(__match_mode, __i); break;
> >>+ __next = _M_handle_accept(__match_mode, __i); break;
> >> case _S_opcode_alternative:
> >>- _M_handle_alternative(__match_mode, __i); break;
> >>+ __next = _M_handle_alternative(__match_mode, __i); break;
> >> default:
> >> __glibcxx_assert(false);
> >> }
> >>+ if (_M_search_mode == _Search_mode::_BFS)
> >>+ {
> >>+ if (__next != _S_invalid_state_id)
> >>+ _M_frames.emplace_back(_S_fopcode_next, __next);
> >>+ return _S_invalid_state_id;
> >>+ }
> >>+ else
> >>+ return __next;
> >> }
> >>
> >> template<typename _BiIter, typename _Alloc, typename _TraitsT>
> >> void _Executor<_BiIter, _Alloc, _TraitsT>::
> >> _M_dfs(_Match_mode __match_mode, _StateIdT __start)
> >> {
> >>- const bool __dfs_mode = (_M_search_mode == _Search_mode::_DFS);
> >> _M_frames.emplace_back(_S_fopcode_next, __start);
> >>
> >> while (!_M_frames.empty())
> >>@@ -621,27 +678,49 @@ namespace __detail
> >> case _S_fopcode_fallback_next:
> >> if (_M_has_sol)
> >> break;
> >>- if (__dfs_mode)
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >> _M_current = __frame._M_pos;
> >> [[__fallthrough__]];
> >> case _S_fopcode_next:
> >>- _M_node(__match_mode, __frame._M_state_id);
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >>+ // Follow immediate successors without re-entering the frame
> >>+ // loop until we fail. This avoids the needless state save and
> >>+ // restore through memory.
> >>+ for (_StateIdT __next = __frame._M_state_id;
> >>+ __next != _S_invalid_state_id;)
> >>+ __next = _M_node(__match_mode, __next);
> >>+ else
> >>+ _M_node(__match_mode, __frame._M_state_id);
> >> break;
> >>
> >> case _S_fopcode_fallback_rep_once_more:
> >> if (_M_has_sol)
> >> break;
> >>- if (__dfs_mode)
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >> _M_current = __frame._M_pos;
> >> [[__fallthrough__]];
> >> case _S_fopcode_rep_once_more:
> >>- _M_rep_once_more(__match_mode, __frame._M_state_id);
> >>+ {
> >>+ _StateIdT __next
> >>+ = _M_rep_once_more(__match_mode,
> __frame._M_state_id);
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >>+ // _M_rep_once_more returned the repeated body's start
> state.
> >>+ // Continue directly in DFS; BFS must materialize the state as
> >>+ // a queue/frame item because it advances by input position
> >>+ // rather than by backtracking order. Splitting this in a
> >>+ // specialized path preserves the behavior for both but for
> >>+ // DFS it avoids the intermediate allocations.
> >>+ for (; __next != _S_invalid_state_id;)
> >>+ __next = _M_node(__match_mode, __next);
> >>+ else if (__next != _S_invalid_state_id)
> >>+ _M_frames.emplace_back(_S_fopcode_next, __next);
> >>+ }
> >> break;
> >>
> >> case _S_fopcode_posix_alternative:
> >> _M_frames.emplace_back(_S_fopcode_merge_sol, 0,
> _M_has_sol);
> >> _M_frames.emplace_back(_S_fopcode_next,
> __frame._M_state_id);
> >>- if (__dfs_mode)
> >>+ if (_M_search_mode == _Search_mode::_DFS)
> >> _M_current = __frame._M_pos;
> >> _M_has_sol = false;
> >> break;
> >>
> >
