Changes in v4:
- Do not remove the BFS executor. I convinced myself that it's
worthwhile to keep it around. When it works, it has polynomial time
complexity vs DFS's worst case exponential, so getting rid of it
would cause regressions on e.g. PR78276 for users that rely on
regex_constants::__polynomial.
- 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_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 | 7 +
libstdc++-v3/include/bits/regex_executor.tcc | 217 +++++++++++++++----
2 files changed, 179 insertions(+), 45 deletions(-)
diff --git a/libstdc++-v3/include/bits/regex_executor.h
b/libstdc++-v3/include/bits/regex_executor.h
index f9857bfc4c1d..e9af007840bb 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.
*
@@ -142,6 +145,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 +296,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 421e585f39d9..9c24bba01e76 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -55,6 +55,71 @@ 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,
+ };
+
+ 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;
+ };
+ };
+
// 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 +246,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);
}
}
}
@@ -208,23 +274,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 +299,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 +315,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,
@@ -264,13 +329,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,
@@ -280,7 +345,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 +355,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 +365,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 +377,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 +386,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 +477,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 +546,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 +603,75 @@ 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_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 __dfs_mode>
--
2.53.0.rc1.25.g1faf5b085a
