Support escaping in TrigramIndex.

[krasin]

Summary

This is a follow up to r288303, where I have introduced TrigramIndex
to speed up SpecialCaseList for the cases when all rules are
simple wildcards, like *hello*wor.d*.

Here, I add support for escaping, so that it's possible to
specify rules like *c\+\+abi*.

[pcc]

lib/Support/TrigramIndex.cpp

60–68

This part doesn't look right. Neither 'n', 't' nor '0' are special. See: http://llvm-cs.pcc.me.uk/lib/Support/regcomp.c#379

I confirmed it with this passing test:

diff --git a/llvm/unittests/Support/RegexTest.cpp b/llvm/unittests/Support/RegexTest.cpp
index 5e3ce39..e151f47 100644
--- a/llvm/unittests/Support/RegexTest.cpp
+++ b/llvm/unittests/Support/RegexTest.cpp
@@ -171,4 +171,16 @@ TEST_F(RegexTest, MatchInvalid) {
   EXPECT_FALSE(r1.match("X"));
 }
 
+TEST_F(RegexTest, foo) {
+  Regex r1("\\t");
+  EXPECT_TRUE(r1.match("t"));
+  EXPECT_FALSE(r1.match("\t"));
+  Regex r2("\\n");
+  EXPECT_TRUE(r2.match("n"));
+  EXPECT_FALSE(r2.match("\n"));
+  Regex r3("\\0");
+  EXPECT_TRUE(r3.match("0"));
+  EXPECT_FALSE(r3.match("x"));
+}
+
 }

[krasin]

Fix handling escaped symbols: they are all self-escaped in LLVM.

[krasin]

lib/Support/TrigramIndex.cpp

60–68

You're right. Thank you for the catch. Fixed.

[pcc]

lib/Support/TrigramIndex.cpp

60–68

What about '1' through '9'?

diff --git a/llvm/unittests/Support/RegexTest.cpp b/llvm/unittests/Support/RegexTest.cpp
index 5e3ce39..bc4995f 100644
--- a/llvm/unittests/Support/RegexTest.cpp
+++ b/llvm/unittests/Support/RegexTest.cpp
@@ -171,4 +171,19 @@ TEST_F(RegexTest, MatchInvalid) {
   EXPECT_FALSE(r1.match("X"));
 }
 
+TEST_F(RegexTest, foo) {
+  Regex r1("\\t");
+  EXPECT_TRUE(r1.match("t"));
+  EXPECT_FALSE(r1.match("\t"));
+  Regex r2("\\n");
+  EXPECT_TRUE(r2.match("n"));
+  EXPECT_FALSE(r2.match("\n"));
+  Regex r3("\\0");
+  EXPECT_TRUE(r3.match("0"));
+  EXPECT_FALSE(r3.match("x"));
+  Regex r4("(a)\\1");
+  EXPECT_TRUE(r4.match("aa"));
+  EXPECT_FALSE(r4.match("a1"));
+}
+
 }

[krasin]

Add backreferences back (except \0).

[krasin]

lib/Support/TrigramIndex.cpp

60–68

I have added \1 to \9 back, and also added tests for these cases.

[pcc]

lib/Support/TrigramIndex.cpp

59–68

Perhaps more simply:

if (Escaped && Char >= '1' && Char <= '9') {
  Defeated = true;
  return;
}

[krasin]

switch -> if

[pcc]

lib/Support/TrigramIndex.cpp

30

Nit: nullptr.

unittests/Support/TrigramIndexTest.cpp

113

I think this is being defeated because of your use of parens, rather than the \1 (which I think should really be \\1).

119

Same here.

[krasin]

NULL -> nullptr; fix the backreferences test cases.

[pcc]

LGTM

lib/Support/TrigramIndex.cpp

 #include <unordered_map>
 #include <set>
 #include <string>
 
 using namespace llvm;
 
 static const char RegexAdvancedMetachars[] = "()^$|+?[]\\{}";
 
-static bool isSimpleWildcard(StringRef Str) {
-  // Check for regex metacharacters other than '*' and '.'.
-  return Str.find_first_of(RegexAdvancedMetachars) == StringRef::npos;
+static bool isAdvancedMetachar(unsigned Char) {
+  return strchr(RegexAdvancedMetachars, Char) != nullptr;
 }
 
 void TrigramIndex::insert(std::string Regex) {
   if (Defeated) return;
-  if (!isSimpleWildcard(Regex)) {
-    Defeated = true;
-    return;
-  }
-
   std::set<unsigned> Was;
   unsigned Cnt = 0;
   unsigned Tri = 0;
   unsigned Len = 0;
+  bool Escaped = false;
   for (unsigned Char : Regex) {
+    if (!Escaped) {
+      // Regular expressions allow escaping symbols by preceding it with '\'.
+      if (Char == '\\') {
+        Escaped = true;
+        continue;
+      }
+      if (isAdvancedMetachar(Char)) {
+        // This is a more complicated regex than we can handle here.
+        Defeated = true;
+        return;
+      }
       if (Char == '.' || Char == '*') {
         Tri = 0;
         Len = 0;
         continue;
       }
+    }
+    if (Escaped && Char >= '1' && Char <= '9') {
+      Defeated = true;
+      return;
+    }
+    // We have already handled escaping and can reset the flag.
+    Escaped = false;
     Tri = ((Tri << 8) + Char) & 0xFFFFFF;
     Len++;
     if (Len < 3)
       continue;
     // We don't want the index to grow too much for the popular trigrams,
     // as they are weak signals. It's ok to still require them for the
     // rules we have already processed. It's just a small additional
     // computational cost.
     if (Index[Tri].size() >= 4)
       continue;
     Cnt++;
     if (!Was.count(Tri)) {
       // Adding the current rule to the index.

unittests/Support/SpecialCaseListTest.cpp

std::unique_ptr<SpecialCaseList> SCL = makeSpecialCaseList("fun:*aaaaaa*\n"
                                                              "fun:*aaaaa*\n"
                                                              "fun:*aaaa*\n"
                                                              "fun:*aaa*\n");
   EXPECT_TRUE(SCL->inSection("fun", "aaa"));
   EXPECT_TRUE(SCL->inSection("fun", "aaaa"));
   EXPECT_TRUE(SCL->inSection("fun", "aaaabbbaaa"));
 }
 
+TEST_F(SpecialCaseListTest, EscapedSymbols) {
+  std::unique_ptr<SpecialCaseList> SCL = makeSpecialCaseList("src:*c\\+\\+abi*\n"
+                                                             "src:*hello\\\\world*\n");
+  EXPECT_TRUE(SCL->inSection("src", "dir/c++abi"));
+  EXPECT_FALSE(SCL->inSection("src", "dir/c\\+\\+abi"));
+  EXPECT_FALSE(SCL->inSection("src", "c\\+\\+abi"));
+  EXPECT_TRUE(SCL->inSection("src", "C:\\hello\\world"));
+  EXPECT_TRUE(SCL->inSection("src", "hello\\world"));
+  EXPECT_FALSE(SCL->inSection("src", "hello\\\\world"));
+}
+
 }

unittests/Support/TrigramIndexTest.cpp

 }
 
 TEST_F(TrigramIndexTest, TooComplicatedRegex2) {
   std::unique_ptr<TrigramIndex> TI =
       makeTrigramIndex({"foo|bar"});
   EXPECT_TRUE(TI->isDefeated());
 }
 
-TEST_F(TrigramIndexTest, SpecialSymbol) {
+TEST_F(TrigramIndexTest, EscapedSymbols) {
   std::unique_ptr<TrigramIndex> TI =
-      makeTrigramIndex({"*c\\+\\+*"});
+      makeTrigramIndex({"*c\\+\\+*", "*hello\\\\world*", "a\\tb", "a\\0b"});
+  EXPECT_FALSE(TI->isDefeated());
+  EXPECT_FALSE(TI->isDefinitelyOut("c++"));
+  EXPECT_TRUE(TI->isDefinitelyOut("c\\+\\+"));
+  EXPECT_FALSE(TI->isDefinitelyOut("hello\\world"));
+  EXPECT_TRUE(TI->isDefinitelyOut("hello\\\\world"));
+  EXPECT_FALSE(TI->isDefinitelyOut("atb"));
+  EXPECT_TRUE(TI->isDefinitelyOut("a\\tb"));
+  EXPECT_TRUE(TI->isDefinitelyOut("a\tb"));
+  EXPECT_FALSE(TI->isDefinitelyOut("a0b"));
+}
+
+TEST_F(TrigramIndexTest, Backreference1) {
+  std::unique_ptr<TrigramIndex> TI =
+      makeTrigramIndex({"*foo\\1*"});
+  EXPECT_TRUE(TI->isDefeated());
+}
+
+TEST_F(TrigramIndexTest, Backreference2) {
+  std::unique_ptr<TrigramIndex> TI =
+      makeTrigramIndex({"*foo\\2*"});
   EXPECT_TRUE(TI->isDefeated());
 }
 
 TEST_F(TrigramIndexTest, Sequence) {
   std::unique_ptr<TrigramIndex> TI =
       makeTrigramIndex({"class1.h", "class2.h", "class3.h", "class4.h"});
   EXPECT_FALSE(TI->isDefeated());
   EXPECT_FALSE(TI->isDefinitelyOut("class1"));
   EXPECT_TRUE(TI->isDefinitelyOut("class.h"));
   EXPECT_TRUE(TI->isDefinitelyOut("class"));
 }
 
 }  // namespace