Apply D28224: 'Throw exception after too many steps' Fixes PR#20291. Thanks to Tim Shen for the patch

llvm-svn: 313056

3 files changed, 112 insertions, 0 deletions

diff --git a/libcxx/include/regex b/libcxx/include/regex
index 77ca648109b..dfc97c58a3f 100644
--- a/libcxx/include/regex
+++ b/libcxx/include/regex
@@ -773,6 +773,8 @@ _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 
+#define _LIBCPP_REGEX_COMPLEXITY_FACTOR 4096
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace regex_constants
@@ -5552,8 +5554,14 @@ basic_regex<_CharT, _Traits>::__match_at_start_ecma(
         __states.back().__node_ = __st;
         __states.back().__flags_ = __flags;
         __states.back().__at_first_ = __at_first;
+        int __counter = 0;
+        int __length = __last - __first;
         do
         {
+            ++__counter;
+            if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
+                __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
+              __throw_regex_error<regex_constants::error_complexity>();
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
@@ -5627,8 +5635,14 @@ basic_regex<_CharT, _Traits>::__match_at_start_posix_nosubs(
         __states.back().__flags_ = __flags;
         __states.back().__at_first_ = __at_first;
         bool __matched = false;
+        int __counter = 0;
+        int __length = __last - __first;
         do
         {
+            ++__counter;
+            if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
+                __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
+              __throw_regex_error<regex_constants::error_complexity>();
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
@@ -5724,8 +5738,14 @@ basic_regex<_CharT, _Traits>::__match_at_start_posix_subs(
         __states.back().__at_first_ = __at_first;
         const _CharT* __current = __first;
         bool __matched = false;
+        int __counter = 0;
+        int __length = __last - __first;
         do
         {
+            ++__counter;
+            if (__counter % _LIBCPP_REGEX_COMPLEXITY_FACTOR == 0 &&
+                __counter / _LIBCPP_REGEX_COMPLEXITY_FACTOR >= __length)
+              __throw_regex_error<regex_constants::error_complexity>();
             __state& __s = __states.back();
             if (__s.__node_)
                 __s.__node_->__exec(__s);
diff --git a/libcxx/test/std/re/re.alg/re.alg.match/exponential.pass.cpp b/libcxx/test/std/re/re.alg/re.alg.match/exponential.pass.cpp
new file mode 100644
index 00000000000..f7d653c64e9
--- /dev/null
+++ b/libcxx/test/std/re/re.alg/re.alg.match/exponential.pass.cpp
@@ -0,0 +1,46 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// template <class BidirectionalIterator, class Allocator, class charT, class traits>
+//     bool
+//     regex_match(BidirectionalIterator first, BidirectionalIterator last,
+//                  match_results<BidirectionalIterator, Allocator>& m,
+//                  const basic_regex<charT, traits>& e,
+//                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+// Throw exception after spent too many cycles with respect to the length of the input string.
+
+#include <regex>
+#include <cassert>
+
+int main() {
+  for (std::regex_constants::syntax_option_type op :
+       {std::regex::ECMAScript, std::regex::extended, std::regex::egrep,
+        std::regex::awk}) {
+    try {
+      std::regex_match(
+          "aaaaaaaaaaaaaaaaaaaa",
+          std::regex(
+              "a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaa",
+              op));
+      assert(false);
+    } catch (const std::regex_error &e) {
+      assert(e.code() == std::regex_constants::error_complexity);
+    }
+  }
+  std::string s(100000, 'a');
+  for (std::regex_constants::syntax_option_type op :
+       {std::regex::ECMAScript, std::regex::extended, std::regex::egrep,
+        std::regex::awk}) {
+    assert(std::regex_match(s, std::regex("a*", op)));
+  }
+  return 0;
+}
diff --git a/libcxx/test/std/re/re.alg/re.alg.search/exponential.pass.cpp b/libcxx/test/std/re/re.alg/re.alg.search/exponential.pass.cpp
new file mode 100644
index 00000000000..c48cc94d148
--- /dev/null
+++ b/libcxx/test/std/re/re.alg/re.alg.search/exponential.pass.cpp
@@ -0,0 +1,46 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// template <class BidirectionalIterator, class Allocator, class charT, class traits>
+//     bool
+//     regex_search(BidirectionalIterator first, BidirectionalIterator last,
+//                  match_results<BidirectionalIterator, Allocator>& m,
+//                  const basic_regex<charT, traits>& e,
+//                  regex_constants::match_flag_type flags = regex_constants::match_default);
+
+// Throw exception after spent too many cycles with respect to the length of the input string.
+
+#include <regex>
+#include <cassert>
+
+int main() {
+  for (std::regex_constants::syntax_option_type op :
+       {std::regex::ECMAScript, std::regex::extended, std::regex::egrep,
+        std::regex::awk}) {
+    try {
+      std::regex_search(
+          "aaaaaaaaaaaaaaaaaaaa",
+          std::regex(
+              "a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaa",
+              op));
+      assert(false);
+    } catch (const std::regex_error &e) {
+      assert(e.code() == std::regex_constants::error_complexity);
+    }
+  }
+  std::string s(100000, 'a');
+  for (std::regex_constants::syntax_option_type op :
+       {std::regex::ECMAScript, std::regex::extended, std::regex::egrep,
+        std::regex::awk}) {
+    assert(std::regex_search(s, std::regex("a*", op)));
+  }
+  return 0;
+}