[Patch 1/3] Use manual regex algorithm switching

[Jonathan Wakely]

>--- a/libstdc++-v3/include/bits/regex.tcc
>+++ b/libstdc++-v3/include/bits/regex.tcc
>@@ -28,12 +28,12 @@
>  *  Do not attempt to use it directly. @headername{regex}
>  */
>
>-// See below __regex_algo_impl to get what this is talking about. The default
>-// value 1 indicated a conservative optimization without giving up worst case
>-// performance.
>-#ifndef _GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT
>-#define _GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT 1
>-#endif
>+// A non-standard switch to let the user pick the matching algorithm.
>+// If _GLIBCXX_REGEX_USE_THOMPSON_NFA is defined, the thompson NFA
>+// algorithm will be used. This algorithm is not by default, and cannot

This should say "not enabled by default" or "not used by default".

>+// be used if the regex contains back-references, but has better
>+// (polynomial instead of exponential) worst case performace.
>+// See __regex_algo_impl below.
>
> namespace std _GLIBCXX_VISIBILITY(default)
> {
>@@ -68,7 +68,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
>       // This function decide which executor to use under given circumstances.
>       // The _S_auto policy now is the following: if a NFA has no
>-      // back-references and has more than _GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT
>+      // back-references and has more than _GLIBCXX_REGEX_USE_THOMPSON_NFA

This comment needs more than just a simple replacement, as the way the
macro is used changed, not just its name.

>       // quantifiers (*, +, ?), the BFS executor will be used, other wise
>       // DFS executor. This is because DFS executor has a exponential upper
>       // bound, but better best-case performace. Meanwhile, BFS executor can
>@@ -82,8 +82,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>       bool __ret;
>       if (!__re._M_automaton->_M_has_backref
> 	  && (__policy == _RegexExecutorPolicy::_S_alternate
>-	      || __re._M_automaton->_M_quant_count
>-		> _GLIBCXX_REGEX_DFS_QUANTIFIERS_LIMIT))
>+#ifdef _GLIBCXX_REGEX_USE_THOMPSON_NFA
>+	      || true
>+#endif
>+	      ))

I wonder if this would be simpler to read like this:

        if (!__re._M_automaton->_M_has_backref
#ifndef _GLIBCXX_REGEX_USE_THOMPSON_NFA
  	   && __policy == _RegexExecutorPolicy::_S_alternate
#endif
           )

What do you think?