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 --
This replaces the recursion and implicit call 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 stack
usage is minimal. Besides reduced stack usage, this should be a
non-functional change. Readability rather than optimal heap usage is
emphasized. There's some low-hanging fruit for optimizing heap usage
that I'll submit as follow-up patches.
Since the signature of _Executor was changed by the previous patch via
the __dfs_mode template parameter removal, and _Executor is an internal
type that users can't name, I believe there's no ABI issues or risks of
mixing old/new version member functions?
PR libstdc++/86164
libstdc++-v3/ChangeLog:
* include/bits/regex_executor.h (__detail::_ExecutorFrame):
Declare.
(__detail::_Executor::_M_node): Declare.
(__detail::_Executor::_M_dfs): Remove __start parameter.
(__detail::_Executor::_M_frames): New data member.
* include/bits/regex_executor.tcc (__detail::_ExecutorFrameOpcode):
New.
(__detail::_ExecutorFrame): New.
(__detail::_Executor::_M_main_dispatch): Adjust _M_dfs call
after _StateId parameter removal.
(__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): Remove _StateIdT parameter. 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.
---
libstdc++-v3/include/bits/regex_executor.h | 9 +-
libstdc++-v3/include/bits/regex_executor.tcc | 226 ++++++++++++++-----
2 files changed, 178 insertions(+), 57 deletions(-)
diff --git a/libstdc++-v3/include/bits/regex_executor.h
b/libstdc++-v3/include/bits/regex_executor.h
index 0c3f7f9050b0..578eccc7e5d9 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -41,6 +41,9 @@ namespace __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.
*/
@@ -135,7 +138,10 @@ namespace __detail
_M_handle_alternative(_Match_mode, _StateIdT);
void
- _M_dfs(_Match_mode __match_mode, _StateIdT __start);
+ _M_node(_Match_mode, _StateIdT);
+
+ void
+ _M_dfs(_Match_mode);
bool
_M_main(_Match_mode __match_mode)
@@ -235,6 +241,7 @@ namespace __detail
};
public:
+ _GLIBCXX_STD_C::vector<_ExecutorFrame<_BiIter>> _M_frames;
_ResultsVec _M_cur_results;
_BiIter _M_current;
_BiIter _M_begin;
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc
b/libstdc++-v3/include/bits/regex_executor.tcc
index 58d5a2bfec3a..f68b3641936e 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -54,15 +54,72 @@ namespace __detail
return false;
}
- // 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.
- //
- // ------------------------------------------------------------
- //
- // DFS mode:
- //
- // It applies a Depth-First-Search (aka backtracking) on given NFA and input
+ 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,
+ };
+
+ template<typename _BiIter, bool _Trivial /* =
is_trivially_copyable<_BiIter>::value */>
+ struct _ExecutorFrame
+ {
+ _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i)
+ : _M_op(__op), _M_state_id(__i)
+ { }
+
+ _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i, _BiIter __p)
+ : _M_op(__op), _M_state_id(__i), _M_pos(__p)
+ { }
+
+ _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i, long __v)
+ : _M_op(__op), _M_state_id(__i), _M_val(__v)
+ { }
+
+ _ExecutorFrameOpcode _M_op;
+ char _M_char;
+ _StateIdT _M_state_id;
+ // _M_pos and _M_val are mutually exclusive, which is more obvious
+ // in the optimized partial specialization below.
+ _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>
+ {
+ _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i)
+ : _M_op(__op), _M_state_id(__i)
+ { }
+
+ _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i, _BiIter __p)
+ : _M_op(__op), _M_state_id(__i), _M_pos(__p)
+ { }
+
+ _ExecutorFrame(_ExecutorFrameOpcode __op, _StateIdT __i, long __v)
+ : _M_op(__op), _M_state_id(__i), _M_val(__v)
+ { }
+
+ _ExecutorFrameOpcode _M_op;
+ char _M_char;
+ _StateIdT _M_state_id;
+ union
+ {
+ _BiIter _M_pos;
+ long _M_val;
+ };
+ };
+
+ // Apply a Depth-First-Search (aka backtracking) on given NFA and input
// string.
// At the very beginning the executor stands in the start state, then it
// tries every possible state transition in current state recursively. Some
@@ -84,7 +141,7 @@ namespace __detail
_M_has_sol = false;
*_M_states._M_get_sol_pos() = _BiIter();
_M_cur_results = _M_results;
- _M_dfs(__match_mode, _M_states._M_start);
+ _M_dfs(__match_mode);
return _M_has_sol;
}
@@ -123,19 +180,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_char = __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);
}
}
}
@@ -149,21 +207,16 @@ 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 we already accepted, we're done.
- 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_rep_once_more, __i);
}
else // Non-greedy 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);
}
}
@@ -172,12 +225,12 @@ 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,
+ __state._M_subexpr, __res.first);
+ _M_frames.back()._M_char = -1;
__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>
@@ -185,13 +238,13 @@ 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,
+ __state._M_subexpr, __res.second);
+ _M_frames.back()._M_char = __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>
@@ -200,36 +253,36 @@ 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>
inline void _Executor<_BiIter, _Alloc, _TraitsT>::
- _M_handle_line_end_assertion(_Match_mode __match_mode, _StateIdT __i)
+ _M_handle_line_end_assertion(_Match_mode, _StateIdT __i)
{
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>
inline void _Executor<_BiIter, _Alloc, _TraitsT>::
- _M_handle_word_boundary(_Match_mode __match_mode, _StateIdT __i)
+ _M_handle_word_boundary(_Match_mode, _StateIdT __i)
{
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.
// We recursively invoke our algorithm to match the sub-NFA.
template<typename _BiIter, typename _Alloc, typename _TraitsT>
void _Executor<_BiIter, _Alloc, _TraitsT>::
- _M_handle_subexpr_lookahead(_Match_mode __match_mode, _StateIdT __i)
+ _M_handle_subexpr_lookahead(_Match_mode, _StateIdT __i)
{
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>
@@ -237,14 +290,13 @@ namespace __detail
_M_handle_match(_Match_mode __match_mode, _StateIdT __i)
{
const auto& __state = _M_nfa[__i];
-
if (_M_current == _M_end)
return;
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);
}
}
@@ -320,13 +372,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);
}
}
@@ -373,29 +424,24 @@ 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)
{
- _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>
void _Executor<_BiIter, _Alloc, _TraitsT>::
- _M_dfs(_Match_mode __match_mode, _StateIdT __i)
+ _M_node(_Match_mode __match_mode, _StateIdT __i)
{
switch (_M_nfa[__i]._M_opcode())
{
@@ -427,6 +473,74 @@ namespace __detail
}
}
+ template<typename _BiIter, typename _Alloc, typename _TraitsT>
+ void _Executor<_BiIter, _Alloc, _TraitsT>::
+ _M_dfs(_Match_mode __match_mode)
+ {
+ _M_frames.emplace_back(_S_fopcode_next, _M_states._M_start);
+
+ while (!_M_frames.empty())
+ {
+ _ExecutorFrame<_BiIter> __frame = std::move(_M_frames.back());
+ _M_frames.pop_back();
+
+ switch (__frame._M_op)
+ {
+ case _S_fopcode_next:
+ _M_node(__match_mode, __frame._M_state_id);
+ break;
+
+ case _S_fopcode_fallback_next:
+ if (!_M_has_sol)
+ _M_frames.emplace_back(_S_fopcode_next, __frame._M_state_id);
+ break;
+
+ case _S_fopcode_fallback_rep_once_more:
+ if (!_M_has_sol)
+ _M_frames.emplace_back(_S_fopcode_rep_once_more,
+ __frame._M_state_id);
+ break;
+
+ 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_char == -1)
+ _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_char;
+ }
+ 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_char;
+ 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 _Executor<_BiIter, _Alloc, _TraitsT>::
--
2.53.0.rc1
