src/third_party/re2/re2/testing/possible_match_test.cc

   1 // Copyright 2006-2008 The RE2 Authors.  All Rights Reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 #include <vector>
   6 #include "util/test.h"
   7 #include "re2/prog.h"
   8 #include "re2/re2.h"
   9 #include "re2/regexp.h"
  10 #include "re2/testing/regexp_generator.h"
  11 #include "re2/testing/string_generator.h"
  12
  13 namespace re2 {
  14
  15 // Test that C++ strings are compared as uint8s, not int8s.
  16 // PossibleMatchRange doesn't depend on this, but callers probably will.
  17 TEST(CplusplusStrings, EightBit) {
  18   string s = "\x70";
  19   string t = "\xA0";
  20   EXPECT_LT(s, t);
  21 }
  22
  23 struct PrefixTest {
  24   const char* regexp;
  25   int maxlen;
  26   const char* min;
  27   const char* max;
  28 };
  29
  30 static PrefixTest tests[] = {
  31   { "",                  10,  "",           "",        },
  32   { "Abcdef",            10,  "Abcdef",     "Abcdef"   },
  33   { "abc(def|ghi)",      10,  "abcdef",     "abcghi"   },
  34   { "a+hello",           10,  "aa",         "ahello"   },
  35   { "a*hello",           10,  "a",          "hello"    },
  36   { "def|abc",           10,  "abc",        "def"      },
  37   { "a(b)(c)[d]",        10,  "abcd",       "abcd"     },
  38   { "ab(cab|cat)",       10,  "abcab",      "abcat"    },
  39   { "ab(cab|ca)x",       10,  "abcabx",     "abcax"    },
  40   { "(ab|x)(c|de)",      10,  "abc",        "xde"      },
  41   { "(ab|x)?(c|z)?",     10,  "",           "z"        },
  42   { "[^\\s\\S]",         10,  "",           ""         },
  43   { "(abc)+",             5,  "abc",        "abcac"    },
  44   { "(abc)+",             2,  "ab",         "ac"       },
  45   { "(abc)+",             1,  "a",          "b"        },
  46   { "[a\xC3\xA1]",        4,  "a",          "\xC3\xA1" },
  47   { "a*",                10,  "",           "ab"       },
  48
  49   { "(?i)Abcdef",        10,  "ABCDEF",     "abcdef"   },
  50   { "(?i)abc(def|ghi)",  10,  "ABCDEF",     "abcghi"   },
  51   { "(?i)a+hello",       10,  "AA",         "ahello"   },
  52   { "(?i)a*hello",       10,  "A",          "hello"    },
  53   { "(?i)def|abc",       10,  "ABC",        "def"      },
  54   { "(?i)a(b)(c)[d]",    10,  "ABCD",       "abcd"     },
  55   { "(?i)ab(cab|cat)",   10,  "ABCAB",      "abcat"    },
  56   { "(?i)ab(cab|ca)x",   10,  "ABCABX",     "abcax"    },
  57   { "(?i)(ab|x)(c|de)",  10,  "ABC",        "xde"      },
  58   { "(?i)(ab|x)?(c|z)?", 10,  "",           "z"        },
  59   { "(?i)[^\\s\\S]",     10,  "",           ""         },
  60   { "(?i)(abc)+",         5,  "ABC",        "abcac"    },
  61   { "(?i)(abc)+",         2,  "AB",         "ac"       },
  62   { "(?i)(abc)+",         1,  "A",          "b"        },
  63   { "(?i)[a\xC3\xA1]",    4,  "A",          "\xC3\xA1" },
  64   { "(?i)a*",            10,  "",           "ab"       },
  65   { "(?i)A*",            10,  "",           "ab"       },
  66
  67   { "\\AAbcdef",         10,  "Abcdef",     "Abcdef"   },
  68   { "\\Aabc(def|ghi)",   10,  "abcdef",     "abcghi"   },
  69   { "\\Aa+hello",        10,  "aa",         "ahello"   },
  70   { "\\Aa*hello",        10,  "a",          "hello"    },
  71   { "\\Adef|abc",        10,  "abc",        "def"      },
  72   { "\\Aa(b)(c)[d]",     10,  "abcd",       "abcd"     },
  73   { "\\Aab(cab|cat)",    10,  "abcab",      "abcat"    },
  74   { "\\Aab(cab|ca)x",    10,  "abcabx",     "abcax"    },
  75   { "\\A(ab|x)(c|de)",   10,  "abc",        "xde"      },
  76   { "\\A(ab|x)?(c|z)?",  10,  "",           "z"        },
  77   { "\\A[^\\s\\S]",      10,  "",           ""         },
  78   { "\\A(abc)+",          5,  "abc",        "abcac"    },
  79   { "\\A(abc)+",          2,  "ab",         "ac"       },
  80   { "\\A(abc)+",          1,  "a",          "b"        },
  81   { "\\A[a\xC3\xA1]",     4,  "a",          "\xC3\xA1" },
  82   { "\\Aa*",             10,  "",           "ab"       },
  83
  84   { "(?i)\\AAbcdef",         10,  "ABCDEF",     "abcdef"   },
  85   { "(?i)\\Aabc(def|ghi)",   10,  "ABCDEF",     "abcghi"   },
  86   { "(?i)\\Aa+hello",        10,  "AA",         "ahello"   },
  87   { "(?i)\\Aa*hello",        10,  "A",          "hello"    },
  88   { "(?i)\\Adef|abc",        10,  "ABC",        "def"      },
  89   { "(?i)\\Aa(b)(c)[d]",     10,  "ABCD",       "abcd"     },
  90   { "(?i)\\Aab(cab|cat)",    10,  "ABCAB",      "abcat"    },
  91   { "(?i)\\Aab(cab|ca)x",    10,  "ABCABX",     "abcax"    },
  92   { "(?i)\\A(ab|x)(c|de)",   10,  "ABC",        "xde"      },
  93   { "(?i)\\A(ab|x)?(c|z)?",  10,  "",           "z"        },
  94   { "(?i)\\A[^\\s\\S]",      10,  "",           ""         },
  95   { "(?i)\\A(abc)+",          5,  "ABC",        "abcac"    },
  96   { "(?i)\\A(abc)+",          2,  "AB",         "ac"       },
  97   { "(?i)\\A(abc)+",          1,  "A",          "b"        },
  98   { "(?i)\\A[a\xC3\xA1]",     4,  "A",          "\xC3\xA1" },
  99   { "(?i)\\Aa*",             10,  "",           "ab"       },
 100   { "(?i)\\AA*",             10,  "",           "ab"       },
 101 };
 102
 103 TEST(PossibleMatchRange, HandWritten) {
 104   for (int i = 0; i < arraysize(tests); i++) {
 105     for (int j = 0; j < 2; j++) {
 106       const PrefixTest& t = tests[i];
 107       string min, max;
 108       if (j == 0) {
 109         LOG(INFO) << "Checking regexp=" << CEscape(t.regexp);
 110         Regexp* re = Regexp::Parse(t.regexp, Regexp::LikePerl, NULL);
 111         CHECK(re);
 112         Prog* prog = re->CompileToProg(0);
 113         CHECK(prog);
 114         CHECK(prog->PossibleMatchRange(&min, &max, t.maxlen))
 115           << " " << t.regexp;
 116         delete prog;
 117         re->Decref();
 118       } else {
 119         CHECK(RE2(t.regexp).PossibleMatchRange(&min, &max, t.maxlen));
 120       }
 121       EXPECT_EQ(t.min, min) << t.regexp;
 122       EXPECT_EQ(t.max, max) << t.regexp;
 123     }
 124   }
 125 }
 126
 127 // Test cases where PossibleMatchRange should return false.
 128 TEST(PossibleMatchRange, Failures) {
 129   string min, max;
 130
 131   // Fails because no room to write max.
 132   EXPECT_FALSE(RE2("abc").PossibleMatchRange(&min, &max, 0));
 133
 134   // Fails because there is no max -- any non-empty string matches
 135   // or begins a match.  Have to use Latin-1 input, because there
 136   // are no valid UTF-8 strings beginning with byte 0xFF.
 137   EXPECT_FALSE(RE2("[\\s\\S]+", RE2::Latin1).
 138                PossibleMatchRange(&min, &max, 10))
 139     << "min=" << CEscape(min) << ", max=" << CEscape(max);
 140   EXPECT_FALSE(RE2("[\\0-\xFF]+", RE2::Latin1).
 141                PossibleMatchRange(&min, &max, 10))
 142     << "min=" << CEscape(min) << ", max=" << CEscape(max);
 143   EXPECT_FALSE(RE2(".+hello", RE2::Latin1).
 144                PossibleMatchRange(&min, &max, 10))
 145     << "min=" << CEscape(min) << ", max=" << CEscape(max);
 146   EXPECT_FALSE(RE2(".*hello", RE2::Latin1).
 147                PossibleMatchRange(&min, &max, 10))
 148     << "min=" << CEscape(min) << ", max=" << CEscape(max);
 149   EXPECT_FALSE(RE2(".*", RE2::Latin1).
 150                PossibleMatchRange(&min, &max, 10))
 151     << "min=" << CEscape(min) << ", max=" << CEscape(max);
 152   EXPECT_FALSE(RE2("\\C*").
 153                PossibleMatchRange(&min, &max, 10))
 154     << "min=" << CEscape(min) << ", max=" << CEscape(max);
 155
 156   // Fails because it's a malformed regexp.
 157   EXPECT_FALSE(RE2("*hello").PossibleMatchRange(&min, &max, 10))
 158     << "min=" << CEscape(min) << ", max=" << CEscape(max);
 159 }
 160
 161 // Exhaustive test: generate all regexps within parameters,
 162 // then generate all strings of a given length over a given alphabet,
 163 // then check that the prefix information agrees with whether
 164 // the regexp matches each of the strings.
 165 class PossibleMatchTester : public RegexpGenerator {
 166  public:
 167   PossibleMatchTester(int maxatoms,
 168                       int maxops,
 169                       const vector<string>& alphabet,
 170                       const vector<string>& ops,
 171                       int maxstrlen,
 172                       const vector<string>& stralphabet)
 173     : RegexpGenerator(maxatoms, maxops, alphabet, ops),
 174       strgen_(maxstrlen, stralphabet),
 175       regexps_(0), tests_(0) { }
 176
 177   int regexps()  { return regexps_; }
 178   int tests()    { return tests_; }
 179
 180   // Needed for RegexpGenerator interface.
 181   void HandleRegexp(const string& regexp);
 182
 183  private:
 184   StringGenerator strgen_;
 185
 186   int regexps_;   // Number of HandleRegexp calls
 187   int tests_;     // Number of regexp tests.
 188
 189   DISALLOW_EVIL_CONSTRUCTORS(PossibleMatchTester);
 190 };
 191
 192 // Processes a single generated regexp.
 193 // Checks that all accepted strings agree with the prefix range.
 194 void PossibleMatchTester::HandleRegexp(const string& regexp) {
 195   regexps_++;
 196
 197   VLOG(3) << CEscape(regexp);
 198
 199   RE2 re(regexp, RE2::Latin1);
 200   CHECK_EQ(re.error(), "");
 201
 202   string min, max;
 203   if(!re.PossibleMatchRange(&min, &max, 10)) {
 204     // There's no good max for "\\C*".  Can't use strcmp
 205     // because sometimes it gets embedded in more
 206     // complicated expressions.
 207     if(strstr(regexp.c_str(), "\\C*"))
 208       return;
 209     LOG(QFATAL) << "PossibleMatchRange failed on: " << CEscape(regexp);
 210   }
 211
 212   strgen_.Reset();
 213   while (strgen_.HasNext()) {
 214     const StringPiece& s = strgen_.Next();
 215     tests_++;
 216     if (!RE2::FullMatch(s, re))
 217       continue;
 218     CHECK_GE(s, min) << " regexp: " << regexp << " max: " << max;
 219     CHECK_LE(s, max) << " regexp: " << regexp << " min: " << min;
 220   }
 221 }
 222
 223 TEST(PossibleMatchRange, Exhaustive) {
 224   int natom = 3;
 225   int noperator = 3;
 226   int stringlen = 5;
 227   if (DEBUG_MODE) {
 228     natom = 2;
 229     noperator = 3;
 230     stringlen = 3;
 231   }
 232   PossibleMatchTester t(natom, noperator, Split(" ", "a b [0-9]"),
 233                  RegexpGenerator::EgrepOps(),
 234                  stringlen, Explode("ab4"));
 235   t.Generate();
 236   LOG(INFO) << t.regexps() << " regexps, "
 237             << t.tests() << " tests";
 238 }
 239
 240 }  // namespace re2