[PATCH v8 1/2] libstdc++/regex: Make DFS executor non-recursive [PR86164]
Jonathan Wakely
jwakely@redhat.com
Fri Jan 30 16:30:30 GMT 2026
On Fri, 30 Jan 2026 at 16:18, Patrick Palka <ppalka@redhat.com> wrote:
>
> On Fri, 30 Jan 2026, Jonathan Wakely wrote:
>
> > On Fri, 30 Jan 2026 at 15:25, Patrick Palka <ppalka@redhat.com> 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.
OK, thanks (for both patches)
>
> 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 <tkaminsk@redhat.com>
> Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
> ---
> 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
More information about the Libstdc++
mailing list