2013-07-31 Tim Shen <timshen91@gmail.com>

	Thompson matcher refactored. Fix grouping problem.
	* include/bits/regex.h: Use a dispatcher _M_get_matcher().
	* include/bits/regex_compiler.h: Tweak for auto switching.
	* include/bits/regex_grep_matcher.h: Class structure.
	* include/bits/regex_grep_matcher.tcc: _BFSMatcher(Thompson
	matcher) refactoring.
	* include/bits/regex_nfa.h: Change _Results's interfaces.
	* include/std/regex: Includes <map> and <queue>.
	* testsuite/28_regex/algorithms/regex_match/extended/53622.cc:
	For both matchers.
	* testsuite/28_regex/algorithms/regex_match/extended/57173.cc:
	For both matchers.
	* testsuite/28_regex/algorithms/regex_match/extended/
	string_dispatch_01.cc: New.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@201358 138bc75d-0d04-0410-961f-82ee72b054a4

3 files changed, 113 insertions, 16 deletions

diff --git a/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/53622.cc b/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/53622.cc
index 383ed054a90..10e2ff43765 100644
--- a/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/53622.cc
+++ b/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/53622.cc
@@ -32,16 +32,31 @@ test01()
 {
   bool test __attribute__((unused)) = true;
 
-  std::regex  re("zxcv/(one.*)abc", std::regex::extended);
-  std::string target("zxcv/onetwoabc");
-  std::smatch m;
-
-  VERIFY( std::regex_search(target, m, re) );
-  VERIFY( m.size() == 2 );
-  VERIFY( m[0].matched == true );
-  VERIFY( std::string(m[0].first, m[0].second) == "zxcv/onetwoabc" );
-  VERIFY( m[1].matched == true );
-  VERIFY( std::string(m[1].first, m[1].second) == "onetwo" );
+  {
+    std::regex  re("zxcv/(one.*)abc", std::regex::extended);
+    std::string target("zxcv/onetwoabc");
+    std::smatch m;
+
+    VERIFY( std::regex_search(target, m, re) );
+    VERIFY( m.size() == 2 );
+    VERIFY( m[0].matched == true );
+    VERIFY( std::string(m[0].first, m[0].second) == "zxcv/onetwoabc" );
+    VERIFY( m[1].matched == true );
+    VERIFY( std::string(m[1].first, m[1].second) == "onetwo" );
+  }
+
+  {
+    std::regex  re("zxcv/(one.*)abc()\\2", std::regex::extended);
+    std::string target("zxcv/onetwoabc");
+    std::smatch m;
+
+    VERIFY( std::regex_search(target, m, re) );
+    VERIFY( m.size() == 3 );
+    VERIFY( m[0].matched == true );
+    VERIFY( std::string(m[0].first, m[0].second) == "zxcv/onetwoabc" );
+    VERIFY( m[1].matched == true );
+    VERIFY( std::string(m[1].first, m[1].second) == "onetwo" );
+  }
 }
 
 int
diff --git a/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/57173.cc b/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/57173.cc
index 3031c43d188..cb3a54f4d88 100644
--- a/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/57173.cc
+++ b/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/57173.cc
@@ -33,13 +33,24 @@ test01()
 {
   bool test __attribute__((unused)) = true;
 
-  std::regex  re("/asdf(/.*)", std::regex::extended);
-  std::string target("/asdf/qwerty");
-  std::smatch m;
+  {
+    std::regex  re("/asdf(/.*)", std::regex::extended);
+    std::string target("/asdf/qwerty");
+    std::smatch m;
 
-  VERIFY( std::regex_match(target, m, re) );
-  VERIFY( m.size() == 2 );
-  VERIFY( std::string(m[1].first, m[1].second) == "/qwerty");
+    VERIFY( std::regex_match(target, m, re) );
+    VERIFY( m.size() == 2 );
+    VERIFY( std::string(m[1].first, m[1].second) == "/qwerty");
+  }
+  {
+    std::regex  re("/asdf(/.*)()\\2", std::regex::extended);
+    std::string target("/asdf/qwerty");
+    std::smatch m;
+
+    VERIFY( std::regex_match(target, m, re) );
+    VERIFY( m.size() == 3 );
+    VERIFY( std::string(m[1].first, m[1].second) == "/qwerty");
+  }
 }
 
 int
diff --git a/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/string_dispatch_01.cc b/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/string_dispatch_01.cc
new file mode 100644
index 00000000000..86fab85a434
--- /dev/null
+++ b/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/string_dispatch_01.cc
@@ -0,0 +1,71 @@
+// { dg-options "-std=gnu++11" }
+
+//
+// 2013-07-29  Tim Shen <timshen91@gmail.com>
+//
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// 28.11.2 regex_match
+// Tests Extended automatic matcher dispatching against a std::string target.
+
+#include <regex>
+#include <testsuite_hooks.h>
+
+using namespace std;
+
+template<typename _Bi_iter, typename _Alloc,
+         typename _Ch_type, typename _Rx_traits>
+  void
+  fake_match(_Bi_iter                                 __s,
+             _Bi_iter                                 __e,
+             match_results<_Bi_iter, _Alloc>&         __m,
+             const basic_regex<_Ch_type, _Rx_traits>& __re,
+             regex_constants::match_flag_type         __flags
+                            = regex_constants::match_default)
+  {
+    __detail::_AutomatonPtr __a = __re._M_get_automaton();
+    __detail::_Automaton::_SizeT __sz = __a->_M_sub_count();
+    __detail::_SpecializedCursor<_Bi_iter> __cs(__s, __e);
+    __detail::_SpecializedResults<_Bi_iter, _Alloc> __r(__sz, __cs, __m);
+    VERIFY( dynamic_cast<__detail::_DFSMatcher *>(
+              &*__a->_M_get_matcher(__cs, __r, __a, __flags)) != nullptr );
+  }
+
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  regex  re("()(one(.*))abc\\1"); // backref cause DFS
+  const string target("onetwoabc");
+  smatch m;
+  fake_match(target.begin(), target.end(), m, re);
+
+  regex_match(target, m, re);
+  VERIFY( m[2].matched );
+  VERIFY( m[3].matched );
+  VERIFY( std::string(m[2].first, m[2].second) == "onetwo" );
+  VERIFY( std::string(m[3].first, m[3].second) == "two" );
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}