Add backreference matching capabilities to Support/Regex, with

appropriate unit tests. This change in itself is not expected to
affect any functionality at this point, but it will serve as a
stepping stone to improve FileCheck's variable matching capabilities.

Luckily, our regex implementation already supports backreferences,
although a bit of hacking is required to enable it. It supports both
Basic Regular Expressions (BREs) and Extended Regular Expressions
(EREs), without supporting backrefs for EREs, following POSIX strictly
in this respect. And EREs is what we actually use (rightly). This is
contrary to many implementations (including the default on Linux) of
POSIX regexes, that do allow backrefs in EREs.

Adding backref support to our EREs is a very simple change in the
regcomp parsing code. I fail to think of significant cases where it
would clash with existing things, and can bring more versatility to
the regexes we write. There's always the danger of a backref in a
specially crafted regex causing exponential matching times, but since
we mainly use them for testing purposes I don't think it's a big
problem. [it can also be placed behind a flag specific to FileCheck,
if needed].

For more details, see:

* http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-November/055840.html
* http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20121126/156878.html



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168802 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 22 insertions, 1 deletions

diff --git a/unittests/Support/RegexTest.cpp b/unittests/Support/RegexTest.cpp
index 65b66c3eee..38d95955f8 100644
--- a/unittests/Support/RegexTest.cpp
+++ b/unittests/Support/RegexTest.cpp
@@ -51,7 +51,6 @@ TEST_F(RegexTest, Basics) {
   EXPECT_EQ(1u, Matches.size());
   EXPECT_EQ(String, Matches[0].str());
 
-
   std::string NulPattern="X[0-9]+X([a-f])?:([0-9]+)";
   String="YX99a:513b";
   NulPattern[7] = '\0';
@@ -62,6 +61,28 @@ TEST_F(RegexTest, Basics) {
   EXPECT_TRUE(r5.match(String));
 }
 
+TEST_F(RegexTest, Backreferences) {
+  Regex r1("([a-z]+)_\\1");
+  SmallVector<StringRef, 4> Matches;
+  EXPECT_TRUE(r1.match("abc_abc", &Matches));
+  EXPECT_EQ(2u, Matches.size());
+  EXPECT_FALSE(r1.match("abc_ab", &Matches));
+
+  Regex r2("a([0-9])b\\1c\\1");
+  EXPECT_TRUE(r2.match("a4b4c4", &Matches));
+  EXPECT_EQ(2u, Matches.size());
+  EXPECT_EQ("4", Matches[1].str());
+  EXPECT_FALSE(r2.match("a2b2c3"));
+
+  Regex r3("a([0-9])([a-z])b\\1\\2");
+  EXPECT_TRUE(r3.match("a6zb6z", &Matches));
+  EXPECT_EQ(3u, Matches.size());
+  EXPECT_EQ("6", Matches[1].str());
+  EXPECT_EQ("z", Matches[2].str());
+  EXPECT_FALSE(r3.match("a6zb6y"));
+  EXPECT_FALSE(r3.match("a6zb7z"));
+}
+
 TEST_F(RegexTest, Substitution) {
   std::string Error;