[patch v2 1/4][libstdc++]: Continue with regex DFS traversals without next frames [PR126274]
Jonathan Wakely
jwakely@redhat.com
Wed Jul 29 15:46:54 GMT 2026
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..23fe828078a32194d996aeb3bfc37e2c46513c41 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..ed53df63a5a304f1db04c3519b986f0e5750e3f5 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..23fe828078a32194d996aeb3bfc37e2c46513c41 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.
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.
>> _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..ed53df63a5a304f1db04c3519b986f0e5750e3f5 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;
>>
>
More information about the Libstdc++
mailing list