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

	Reimplment matcher using Depth-first search(backtracking).
	PR libstdc++/53622
	PR libstdc++/57173
	* include/bits/regex.h: regex_match() and regex_search().
	* include/bits/regex_cursor.h: Fix _M_set_pos().
	* include/bits/regex_grep_matcher.h: add _M_dfs_match().
	* include/bits/regex_grep_matcher.tcc: Implement it.
	* testsuite/28_regex/algorithms/regex_match/extended/string_group_01.cc:
	New.
	* testsuite/28_regex/algorithms/regex_match/extended/string_group_02.cc:
	New.
	* testsuite/28_regex/algorithms/regex_search/basic/string_01.cc:
	Remove xfail.


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

3 files changed, 103 insertions, 2 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
new file mode 100644
index 00000000000..383ed054a90
--- /dev/null
+++ b/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/53622.cc
@@ -0,0 +1,52 @@
+// { dg-options "-std=gnu++11" }
+
+//
+// 2013-07-23  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 grouping against a std::string target.
+
+#include <regex>
+#include <testsuite_hooks.h>
+
+// libstdc++/53622
+void
+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" );
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
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
new file mode 100644
index 00000000000..3031c43d188
--- /dev/null
+++ b/libstdc++-v3/testsuite/28_regex/algorithms/regex_match/extended/57173.cc
@@ -0,0 +1,50 @@
+// { dg-options "-std=gnu++11" }
+
+//
+// 2013-07-23  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.3 regex_search
+// Tests Extended against a std::string target.
+
+#include <regex>
+#include <testsuite_hooks.h>
+#include <iostream>
+
+// libstdc++/57173
+void
+test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  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");
+}
+
+int
+main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/28_regex/algorithms/regex_search/basic/string_01.cc b/libstdc++-v3/testsuite/28_regex/algorithms/regex_search/basic/string_01.cc
index f2a7f2104c1..ee487f19836 100644
--- a/libstdc++-v3/testsuite/28_regex/algorithms/regex_search/basic/string_01.cc
+++ b/libstdc++-v3/testsuite/28_regex/algorithms/regex_search/basic/string_01.cc
@@ -1,5 +1,4 @@
 // { dg-options "-std=gnu++11" }
-// { dg-do run { xfail *-*-* } }
 
 //
 // 2013-07-17  Tim Shen <timshen91@gmail.com>
@@ -32,7 +31,7 @@ test01()
 {
   bool test __attribute__((unused)) = true;
 
-  std::regex  re("as(df)", std::regex::basic);
+  std::regex  re("as\\(df\\)", std::regex::basic);
   std::string target("xxasdfyy");
   std::smatch m;