On Fri, 30 Jan 2026, Jonathan Wakely wrote: > On Fri, 30 Jan 2026 at 15:25, Patrick Palka <[email protected]> wrote: > > > > Changes in v8: > > - Use char instead of uint8_t > > - Decompose the first byte of _ExecutorFrame::_M_bytes into an > > anonymous union with code-specific members > > - Use [[__fallthrough__]] instead of // fallthrough > > > > Changes in v7: > > - Make fallback_next and fallback_rep_once_more code paths fall through > > to the next / rep_once_more code paths instead of pushing a frame > > that gets immediately popped. > > > > Changes in v6: > > - Use an inline namespace to give the _Executor class a different > > mangled name since its implementation is no longer compatible with > > the previous recursive one > > - Explicitly cast _M_subexpr to _StateIdT in _M_handle_subexpr_begin/end > > to self-document that what we're storing in _ExecutorFrame::_M_state_id > > isn't really a state id > > - I experimented with using std::deque instead of std::vector for the > > frames stack. > > Upsides: > > - Reduces peak memory use from 50MB to 33MB for the microbenchmark > > regex_match(string(200000, 'a'), "(a|b|c)*") > > due to less unused capacity (vector's 2x growth factor means that > > 50% of the time there will be at least 25% unused capacity) > > - Seems to be as fast as vector > > - Automatically reclaims unused capacity as the stack unwinds > > - No expensive reallocation needed when growing the stack in the > > case of non-trivially-copyable input iterators > > Downsides: > > - deque will allocate/free a chunk of memory whenever crossing a > > chunk boundary (512 elements) in either direction, which could > > degrade performance in rare cases where our stack size hovers > > near a multiple of the chunk boundary. > > - the fixed chunk size means small inputs will use at least > > 512*24 bytes=12kB of memory > > Ultimately it seems using std::deque is better for very large > > inputs, and for small inputs std::vector is slightly better. I'm > > not sure which container to go with, for now I stuck with std::vector. > > (N.B. we seem to be 2x faster than libc++'s std::regex and use 60% > > less memory for the above microbenchmark) > > > > Changes in v5: > > - Replace char _ExecutorFrame::_M_char with > > uint8_t _ExecutorFrame::_M_bytes[7] to fully account for > > the implicit struct padding and make it char size/signedness > > agnostic. > > > > Changes in v4: > > - Do not remove the BFS executor. I convinced myself that it's > > worthwhile to keep it around for backwards compatibility and its > > better time complexity (e.g. for PR78276). > > - However, this means the mangling of _Executor is now the same as > > before (since the __dfs_mode template parameter is no longer gone). > > I believe we need to give this class a different mangling so > > programs that mix old/new std::regex impls continue to work. > > > > Changes in v3: > > > > - Add char _M_char member to _ExecutorFrame (without increasing the > > size of struct thanks to padding) > > - Use it to fix bug in restore_subexpr_end frame code whereby we > > weren't restoring _M_cur_results.matched properly > > - Combine restore_subexpr_begin/end frame codes into one > > restore_cur_results frame code > > - Combine restore_rep_count_val/posn frame codes into single > > restore_rep_count frame_code (this makes the patch 3/4 from v2 > > obsolete) > > - Store the frame stack in the data member _ExecutorFrame::_M_frames > > alongside the rest of the executor state instead of using a local. > > Using a local variable is just more code with no real benefit. > > > > -- >8 -- > > > > libstdc++/regex: Convert DFS executor to use iteration [PR86164] > > > > This replaces the recursion and implicit system stack usage of the DFS > > executor with iteration and an explicit heap-based stack. After this > > patch, we no longer stack overflow on the PR86164 testcases since system > > stack usage is no longer linear with respect to input size. This should > > otherwise be a non-functional change. > > > > PR libstdc++/86164 > > > > libstdc++-v3/ChangeLog: > > > > * include/bits/regex.h (__detail::_Executor): Use inline > > namespace _V2. > > * include/bits/regex_executor.h (__detail::_ExecutorFrame): > > Declare. > > (__detail::_Executor): Use inline namespace _V2. > > (__detail::_Executor::_M_node): Declare. > > (__detail::_Executor::_M_frames): New data member. > > * include/bits/regex_executor.tcc (__detail::_ExecutorFrameOpcode): > > New. > > (__detail::_ExecutorFrame): New. > > (__detail::_Executor): Use inline namespace _V2. > > (__detail::_Executor::_M_rep_once_more): Replace recursive > > _M_dfs calls with an _S_opcode_next frame push, and any tail work > > after such calls with an appropriate frame push. > > (__detail::_M_handle_repeat): Likewise. > > (__detail::_M_handle_subexpr_begin): Likewise. > > (__detail::_M_handle_subexpr_end): Likewise. > > (__detail::_M_handle_line_begin_assertion): Likewise. > > (__detail::_M_handle_line_end_assertion): Likewise. > > (__detail::_M_handle_word_boundary): Likewise. > > (__detail::_M_handle_subexpr_lookahead): Likewise. > > (__detail::_M_handle_match): Likewise. > > (__detail::_M_handle_backref): Likewise. > > (__detail::_M_handle_accept): Likewise. > > (__detail::_M_handle_alternative): Likewise. > > (__detail::_M_node): Factored out from _M_dfs. > > (__detail::_M_dfs): Push an initial frame to _M_frames that > > visits the starting node and pass this stack each subroutine. > > Pop the latest _ExecutorFrame from _M_frames and handle > > appropriately according to its _ExecutorFrameOpcode. Loop until > > _M_frames is empty. > > * include/std/regex: Include <cstdint>. > > --- > > libstdc++-v3/include/bits/regex.h | 2 + > > libstdc++-v3/include/bits/regex_executor.h | 9 + > > libstdc++-v3/include/bits/regex_executor.tcc | 233 +++++++++++++++---- > > 3 files changed, 199 insertions(+), 45 deletions(-) > > > > diff --git a/libstdc++-v3/include/bits/regex.h > > b/libstdc++-v3/include/bits/regex.h > > index 68fb6254f362..5bcb9a447ce2 100644 > > --- a/libstdc++-v3/include/bits/regex.h > > +++ b/libstdc++-v3/include/bits/regex.h > > @@ -61,8 +61,10 @@ namespace __detail > > _RegexExecutorPolicy __policy, > > bool __match_mode); > > > > +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > > template<typename, typename, typename, bool> > > class _Executor; > > +_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) > > > > template<typename _Tp> > > struct __is_contiguous_iter : false_type { }; > > diff --git a/libstdc++-v3/include/bits/regex_executor.h > > b/libstdc++-v3/include/bits/regex_executor.h > > index f9857bfc4c1d..94048e1f632c 100644 > > --- a/libstdc++-v3/include/bits/regex_executor.h > > +++ b/libstdc++-v3/include/bits/regex_executor.h > > @@ -36,11 +36,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > > > namespace __detail > > { > > +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > > /** > > * @addtogroup regex-detail > > * @{ > > */ > > > > + template<typename _BiIter, bool _Trivial = > > is_trivially_copyable<_BiIter>::value> > > + struct _ExecutorFrame; > > + > > /** > > * @brief Takes a regex and an input string and does the matching. > > * > > @@ -142,6 +146,9 @@ namespace __detail > > void > > _M_handle_alternative(_Match_mode, _StateIdT); > > > > + void > > + _M_node(_Match_mode, _StateIdT); > > + > > void > > _M_dfs(_Match_mode __match_mode, _StateIdT __start); > > > > @@ -290,6 +297,7 @@ namespace __detail > > }; > > > > public: > > + _GLIBCXX_STD_C::vector<_ExecutorFrame<_BiIter>> _M_frames; > > _ResultsVec _M_cur_results; > > _BiIter _M_current; > > _BiIter _M_begin; > > @@ -305,6 +313,7 @@ namespace __detail > > }; > > > > ///@} regex-detail > > +_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) > > } // namespace __detail > > _GLIBCXX_END_NAMESPACE_VERSION > > } // namespace std > > diff --git a/libstdc++-v3/include/bits/regex_executor.tcc > > b/libstdc++-v3/include/bits/regex_executor.tcc > > index 421e585f39d9..36c7e05dcdfb 100644 > > --- a/libstdc++-v3/include/bits/regex_executor.tcc > > +++ b/libstdc++-v3/include/bits/regex_executor.tcc > > @@ -36,6 +36,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > > #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr > > namespace __detail > > { > > +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) > > template<typename _BiIter, typename _Alloc, typename _TraitsT, > > bool __dfs_mode> > > bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: > > @@ -55,6 +56,85 @@ namespace __detail > > return false; > > } > > > > + enum _ExecutorFrameOpcode : unsigned char > > + { > > + _S_fopcode_next, > > + _S_fopcode_fallback_next, > > + _S_fopcode_rep_once_more, > > + _S_fopcode_fallback_rep_once_more, > > + _S_fopcode_posix_alternative, > > + _S_fopcode_merge_sol, > > + _S_fopcode_restore_current, > > + _S_fopcode_restore_cur_results, > > + _S_fopcode_restore_rep_count, > > + _S_fopcode_decrement_rep_count, > > + }; > > + > > +#define _GLIBCXX_EXECUTOR_FRAME_BYTES_LAYOUT \ > > + union { \ > > + unsigned char _M_byte0; \ > > + struct { /* rep_count frame */ \ > > + unsigned char _M_count : 2; \ > > + }; \ > > + struct { /* restore_cur_results frame */ \ > > + unsigned char _M_end : 1; \ > > + unsigned char _M_matched : 1; \ > > + }; \ > > + }; \ > > + unsigned char _M_bytes[6] > > Ah, it didn't occur to me that repacing _M_bytes[7] with this union > would need to be spammed out in two places, sorry! > > This patch is OK for trunk, thanks! > > Maybe as a follow-up we can introduce: > > struct _ExecutorFrameBase > { > _ExecutorFrameOpcode _M_op; > ... the union ... > unsigned char _M_bytes[6]; > _StateIdT _M_state_id; > }; > > for the parts that are common to the primary template and the partial > specialization, and then make them both derive from that.
D'oh, using a base class is much cleaner! I'd prefer making this change now rather than as a follow-up. Like so? The second patch is effectively unchanged. Not only is it cleaner, using a base class enables us to store frames such as _S_fopcode_next that don't need the extra _M_val/_M_pos space on a separate stack of _ExecutorFrameBase objects which would help save space. I'll experiment with that. -- >8 -- Subject: [PATCH] libstdc++/regex: Make DFS executor non-recursive [PR86164] MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Changes in v9: - Define _ExecutorFrameBase base class factoring out the common initial layout between the two _ExecutorFrame templates. Reviewed-by: Tomasz Kamiński <[email protected]> Reviewed-by: Jonathan Wakely <[email protected]> --- libstdc++-v3/include/bits/regex.h | 2 + libstdc++-v3/include/bits/regex_executor.h | 9 + libstdc++-v3/include/bits/regex_executor.tcc | 233 +++++++++++++++---- 3 files changed, 199 insertions(+), 45 deletions(-) diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++-v3/include/bits/regex.h index 68fb6254f362..5bcb9a447ce2 100644 --- a/libstdc++-v3/include/bits/regex.h +++ b/libstdc++-v3/include/bits/regex.h @@ -61,8 +61,10 @@ namespace __detail _RegexExecutorPolicy __policy, bool __match_mode); +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) template<typename, typename, typename, bool> class _Executor; +_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) template<typename _Tp> struct __is_contiguous_iter : false_type { }; diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h index f9857bfc4c1d..94048e1f632c 100644 --- a/libstdc++-v3/include/bits/regex_executor.h +++ b/libstdc++-v3/include/bits/regex_executor.h @@ -36,11 +36,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace __detail { +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) /** * @addtogroup regex-detail * @{ */ + template<typename _BiIter, bool _Trivial = is_trivially_copyable<_BiIter>::value> + struct _ExecutorFrame; + /** * @brief Takes a regex and an input string and does the matching. * @@ -142,6 +146,9 @@ namespace __detail void _M_handle_alternative(_Match_mode, _StateIdT); + void + _M_node(_Match_mode, _StateIdT); + void _M_dfs(_Match_mode __match_mode, _StateIdT __start); @@ -290,6 +297,7 @@ namespace __detail }; public: + _GLIBCXX_STD_C::vector<_ExecutorFrame<_BiIter>> _M_frames; _ResultsVec _M_cur_results; _BiIter _M_current; _BiIter _M_begin; @@ -305,6 +313,7 @@ namespace __detail }; ///@} regex-detail +_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) } // namespace __detail _GLIBCXX_END_NAMESPACE_VERSION } // namespace std diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc index 421e585f39d9..b76f1dce952c 100644 --- a/libstdc++-v3/include/bits/regex_executor.tcc +++ b/libstdc++-v3/include/bits/regex_executor.tcc @@ -36,6 +36,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr namespace __detail { +_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) template<typename _BiIter, typename _Alloc, typename _TraitsT, bool __dfs_mode> bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: @@ -55,6 +56,85 @@ namespace __detail return false; } + enum _ExecutorFrameOpcode : unsigned char + { + _S_fopcode_next, + _S_fopcode_fallback_next, + _S_fopcode_rep_once_more, + _S_fopcode_fallback_rep_once_more, + _S_fopcode_posix_alternative, + _S_fopcode_merge_sol, + _S_fopcode_restore_current, + _S_fopcode_restore_cur_results, + _S_fopcode_restore_rep_count, + _S_fopcode_decrement_rep_count, + }; + + struct _ExecutorFrameBase + { + _ExecutorFrameBase(_ExecutorFrameOpcode __op, _StateIdT __i) + : _M_op(__op), _M_state_id(__i) + { } + + _ExecutorFrameOpcode _M_op; + union { + unsigned char _M_byte0; + struct { // Used by restore_rep_count frame + unsigned char _M_count : 2; + }; + struct { // Used by restore_cur_results frame + unsigned char _M_end : 1; + unsigned char _M_matched : 1; + }; + }; + unsigned char _M_bytes[6]; + _StateIdT _M_state_id; + }; + + template<typename _BiIter, bool _Trivial /* = is_trivially_copyable<_BiIter>::value */> + struct _ExecutorFrame : _ExecutorFrameBase + { + _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i) + : _ExecutorFrameBase(__op, __i) + { } + + _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i, _BiIter __p) + : _ExecutorFrameBase(__op, __i), _M_pos(__p) + { } + + _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i, long __v) + : _ExecutorFrameBase(__op, __i), _M_val(__v) + { } + + // _M_pos and _M_val are mutually exclusive, which the optimized + // partial specialization below depends on. + _BiIter _M_pos = _BiIter(); + long _M_val = 0; + }; + + // Space-optimized partial specialization for when the input iterator is + // trivially copyable. + template<typename _BiIter> + struct _ExecutorFrame<_BiIter, true> : _ExecutorFrameBase + { + _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i) + : _ExecutorFrameBase(__op, __i) + { } + + _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i, _BiIter __p) + : _ExecutorFrameBase(__op, __i), _M_pos(__p) + { } + + _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i, long __v) + : _ExecutorFrameBase(__op, __i), _M_val(__v) + { } + + union { + _BiIter _M_pos; + long _M_val; + }; + }; + // The _M_main function operates in different modes, DFS mode or BFS mode, // indicated by template parameter __dfs_mode, and dispatches to one of the // _M_main_dispatch overloads. @@ -181,19 +261,20 @@ namespace __detail auto& __rep_count = _M_rep_count[__i]; if (__rep_count.second == 0 || __rep_count.first != _M_current) { - auto __back = __rep_count; + _M_frames.emplace_back(_S_fopcode_restore_rep_count, + __i, __rep_count.first); + _M_frames.back()._M_count = __rep_count.second; __rep_count.first = _M_current; __rep_count.second = 1; - _M_dfs(__match_mode, __state._M_alt); - __rep_count = __back; + _M_frames.emplace_back(_S_fopcode_next, __state._M_alt); } else { if (__rep_count.second < 2) { __rep_count.second++; - _M_dfs(__match_mode, __state._M_alt); - __rep_count.second--; + _M_frames.emplace_back(_S_fopcode_decrement_rep_count, __i); + _M_frames.emplace_back(_S_fopcode_next, __state._M_alt); } } } @@ -208,23 +289,23 @@ namespace __detail _M_handle_repeat(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; - // Greedy. if (!__state._M_neg) { - _M_rep_once_more(__match_mode, __i); - // If it's DFS executor and already accepted, we're done. - if (!__dfs_mode || !_M_has_sol) - _M_dfs(__match_mode, __state._M_next); + if constexpr (__dfs_mode) + // If it's DFS executor and already accepted, we're done. + _M_frames.emplace_back(_S_fopcode_fallback_next, __state._M_next); + else + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); + _M_frames.emplace_back(_S_fopcode_rep_once_more, __i); } else // Non-greedy mode { if constexpr (__dfs_mode) { // vice-versa. - _M_dfs(__match_mode, __state._M_next); - if (!_M_has_sol) - _M_rep_once_more(__match_mode, __i); + _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i); + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } else { @@ -233,12 +314,11 @@ namespace __detail // be better by attempting its next node. if (!_M_has_sol) { - _M_dfs(__match_mode, __state._M_next); // DON'T attempt anything if it's already accepted. An // accepted state *must* be better than a solution that // matches a non-greedy quantifier one more time. - if (!_M_has_sol) - _M_rep_once_more(__match_mode, __i); + _M_frames.emplace_back(_S_fopcode_fallback_rep_once_more, __i); + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } } } @@ -250,12 +330,13 @@ namespace __detail _M_handle_subexpr_begin(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; - auto& __res = _M_cur_results[__state._M_subexpr]; - auto __back = __res.first; + _M_frames.emplace_back(_S_fopcode_restore_cur_results, + static_cast<_StateIdT>(__state._M_subexpr), + __res.first); + _M_frames.back()._M_end = false; __res.first = _M_current; - _M_dfs(__match_mode, __state._M_next); - __res.first = __back; + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } template<typename _BiIter, typename _Alloc, typename _TraitsT, @@ -264,13 +345,15 @@ namespace __detail _M_handle_subexpr_end(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; - auto& __res = _M_cur_results[__state._M_subexpr]; - auto __back = __res; + _M_frames.emplace_back(_S_fopcode_restore_cur_results, + static_cast<_StateIdT>(__state._M_subexpr), + __res.second); + _M_frames.back()._M_end = true; + _M_frames.back()._M_matched = __res.matched; __res.second = _M_current; __res.matched = true; - _M_dfs(__match_mode, __state._M_next); - __res = __back; + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } template<typename _BiIter, typename _Alloc, typename _TraitsT, @@ -280,7 +363,7 @@ namespace __detail { const auto& __state = _M_nfa[__i]; if (_M_at_begin()) - _M_dfs(__match_mode, __state._M_next); + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } template<typename _BiIter, typename _Alloc, typename _TraitsT, @@ -290,7 +373,7 @@ namespace __detail { const auto& __state = _M_nfa[__i]; if (_M_at_end()) - _M_dfs(__match_mode, __state._M_next); + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } template<typename _BiIter, typename _Alloc, typename _TraitsT, @@ -300,7 +383,7 @@ namespace __detail { const auto& __state = _M_nfa[__i]; if (_M_word_boundary() == !__state._M_neg) - _M_dfs(__match_mode, __state._M_next); + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } // Here __state._M_alt offers a single start node for a sub-NFA. @@ -312,7 +395,7 @@ namespace __detail { const auto& __state = _M_nfa[__i]; if (_M_lookahead(__state._M_alt) == !__state._M_neg) - _M_dfs(__match_mode, __state._M_next); + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } template<typename _BiIter, typename _Alloc, typename _TraitsT, @@ -321,16 +404,15 @@ namespace __detail _M_handle_match(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; - if (_M_current == _M_end) return; if constexpr (__dfs_mode) { if (__state._M_matches(*_M_current)) { + _M_frames.emplace_back(_S_fopcode_restore_current, 0, _M_current); ++_M_current; - _M_dfs(__match_mode, __state._M_next); - --_M_current; + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } } else @@ -413,13 +495,12 @@ namespace __detail { if (__last != _M_current) { - auto __backup = _M_current; + _M_frames.emplace_back(_S_fopcode_restore_current, 0, _M_current); _M_current = __last; - _M_dfs(__match_mode, __state._M_next); - _M_current = __backup; + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } else - _M_dfs(__match_mode, __state._M_next); + _M_frames.emplace_back(_S_fopcode_next, __state._M_next); } } @@ -483,31 +564,26 @@ namespace __detail _M_handle_alternative(_Match_mode __match_mode, _StateIdT __i) { const auto& __state = _M_nfa[__i]; - if (_M_nfa._M_flags & regex_constants::ECMAScript) { // TODO: Fix BFS support. It is wrong. - _M_dfs(__match_mode, __state._M_alt); // Pick lhs if it matches. Only try rhs if it doesn't. - if (!_M_has_sol) - _M_dfs(__match_mode, __state._M_next); + _M_frames.emplace_back(_S_fopcode_fallback_next, __state._M_next); + _M_frames.emplace_back(_S_fopcode_next, __state._M_alt); } else { // Try both and compare the result. // See "case _S_opcode_accept:" handling above. - _M_dfs(__match_mode, __state._M_alt); - auto __has_sol = _M_has_sol; - _M_has_sol = false; - _M_dfs(__match_mode, __state._M_next); - _M_has_sol |= __has_sol; + _M_frames.emplace_back(_S_fopcode_posix_alternative, __state._M_next); + _M_frames.emplace_back(_S_fopcode_next, __state._M_alt); } } template<typename _BiIter, typename _Alloc, typename _TraitsT, bool __dfs_mode> void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: - _M_dfs(_Match_mode __match_mode, _StateIdT __i) + _M_node(_Match_mode __match_mode, _StateIdT __i) { if (_M_states._M_visited(__i)) return; @@ -545,6 +621,72 @@ namespace __detail } } + template<typename _BiIter, typename _Alloc, typename _TraitsT, + bool __dfs_mode> + void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>:: + _M_dfs(_Match_mode __match_mode, _StateIdT __start) + { + _M_frames.emplace_back(_S_fopcode_next, __start); + + while (!_M_frames.empty()) + { + _ExecutorFrame<_BiIter> __frame = std::move(_M_frames.back()); + _M_frames.pop_back(); + + switch (__frame._M_op) + { + case _S_fopcode_fallback_next: + if (_M_has_sol) + break; + [[__fallthrough__]]; + case _S_fopcode_next: + _M_node(__match_mode, __frame._M_state_id); + break; + + case _S_fopcode_fallback_rep_once_more: + if (_M_has_sol) + break; + [[__fallthrough__]]; + case _S_fopcode_rep_once_more: + _M_rep_once_more(__match_mode, __frame._M_state_id); + 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); + _M_has_sol = false; + break; + + case _S_fopcode_merge_sol: + _M_has_sol |= __frame._M_val; + break; + + case _S_fopcode_restore_current: + _M_current = __frame._M_pos; + break; + + case _S_fopcode_restore_cur_results: + if (!__frame._M_end) + _M_cur_results[__frame._M_state_id].first = __frame._M_pos; + else + { + _M_cur_results[__frame._M_state_id].second = __frame._M_pos; + _M_cur_results[__frame._M_state_id].matched = __frame._M_matched; + } + break; + + case _S_fopcode_restore_rep_count: + _M_rep_count[__frame._M_state_id].first = __frame._M_pos; + _M_rep_count[__frame._M_state_id].second = __frame._M_count; + break; + + case _S_fopcode_decrement_rep_count: + _M_rep_count[__frame._M_state_id].second--; + break; + } + } + } + // Return whether now is at some word boundary. template<typename _BiIter, typename _Alloc, typename _TraitsT, bool __dfs_mode> @@ -569,6 +711,7 @@ namespace __detail return __left_is_word != __right_is_word; } +_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) } // namespace __detail #pragma GCC diagnostic pop -- 2.53.0.rc1.65.gea24e2c554
