[Bug libstdc++/78276] regex_search is slow

[redi at gcc dot gnu.org via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78276

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
With this patch:

--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -626,9 +626,16 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
     _M_dfs(_Match_mode __match_mode, _StateIdT __start)
     {
       _M_frames.emplace_back(_S_fopcode_next, __start);
+      unsigned __steps = 0;
+      const auto __dist = std::distance(_M_begin, _M_end);

       while (!_M_frames.empty())
        {
+         ++__steps;
+         if (__steps >> 13 > __dist)
+           __throw_regex_error(regex_constants::error_complexity,
+                               "it's over 9000!");
+
          _ExecutorFrame<_BiIter> __frame = std::move(_M_frames.back());
          _M_frames.pop_back();


GCC rejects both examples in this bug report:

terminate called after throwing an instance of 'std::regex_error'
  what():  it's over 9000!
Aborted (core dumped)