libstdc++/regex: Make DFS executor non-recursive [PR86164]

This patch replaces the recursive implementation of the DFS executor
with an iterative one using an explicit heap-based stack.  System
stack usage of the executor is now constant with respect to input size
rather than linear, avoding stack overflow errors when processing
long inputs.

	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::_ExecutorFrameBase): 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 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.

Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>

0 files changed, 0 insertions, 0 deletions