1 // Copyright 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 // Random testing of regular expression matching.
6
7 #include <string>
8 #include <vector>
9
10 #include "absl/flags/flag.h"
11 #include "absl/strings/str_format.h"
12 #include "gtest/gtest.h"
13 #include "re2/testing/exhaustive_tester.h"
14 #include "re2/testing/regexp_generator.h"
15
16 ABSL_FLAG(int, regexpseed, 404, "Random regexp seed.");
17 ABSL_FLAG(int, regexpcount, 100, "How many random regexps to generate.");
18 ABSL_FLAG(int, stringseed, 200, "Random string seed.");
19 ABSL_FLAG(int, stringcount, 100, "How many random strings to generate.");
20
21 namespace re2 {
22
23 // Runs a random test on the given parameters.
24 // (Always uses the same random seeds for reproducibility.
25 // Can give different seeds on command line.)
RandomTest(int maxatoms,int maxops,const std::vector<std::string> & alphabet,const std::vector<std::string> & ops,int maxstrlen,const std::vector<std::string> & stralphabet,const std::string & wrapper)26 static void RandomTest(int maxatoms, int maxops,
27 const std::vector<std::string>& alphabet,
28 const std::vector<std::string>& ops,
29 int maxstrlen,
30 const std::vector<std::string>& stralphabet,
31 const std::string& wrapper) {
32 // Limit to smaller test cases in debug mode,
33 // because everything is so much slower.
34 if (RE2_DEBUG_MODE) {
35 maxatoms--;
36 maxops--;
37 maxstrlen /= 2;
38 }
39
40 ExhaustiveTester t(maxatoms, maxops, alphabet, ops,
41 maxstrlen, stralphabet, wrapper, "");
42 t.RandomStrings(absl::GetFlag(FLAGS_stringseed),
43 absl::GetFlag(FLAGS_stringcount));
44 t.GenerateRandom(absl::GetFlag(FLAGS_regexpseed),
45 absl::GetFlag(FLAGS_regexpcount));
46 absl::PrintF("%d regexps, %d tests, %d failures [%d/%d str]\n",
47 t.regexps(), t.tests(), t.failures(), maxstrlen, stralphabet.size());
48 EXPECT_EQ(0, t.failures());
49 }
50
51 // Tests random small regexps involving literals and egrep operators.
TEST(Random,SmallEgrepLiterals)52 TEST(Random, SmallEgrepLiterals) {
53 RandomTest(5, 5, Explode("abc."), RegexpGenerator::EgrepOps(),
54 15, Explode("abc"),
55 "");
56 }
57
58 // Tests random bigger regexps involving literals and egrep operators.
TEST(Random,BigEgrepLiterals)59 TEST(Random, BigEgrepLiterals) {
60 RandomTest(10, 10, Explode("abc."), RegexpGenerator::EgrepOps(),
61 15, Explode("abc"),
62 "");
63 }
64
65 // Tests random small regexps involving literals, capturing parens,
66 // and egrep operators.
TEST(Random,SmallEgrepCaptures)67 TEST(Random, SmallEgrepCaptures) {
68 RandomTest(5, 5, Split(" ", "a (b) ."), RegexpGenerator::EgrepOps(),
69 15, Explode("abc"),
70 "");
71 }
72
73 // Tests random bigger regexps involving literals, capturing parens,
74 // and egrep operators.
TEST(Random,BigEgrepCaptures)75 TEST(Random, BigEgrepCaptures) {
76 RandomTest(10, 10, Split(" ", "a (b) ."), RegexpGenerator::EgrepOps(),
77 15, Explode("abc"),
78 "");
79 }
80
81 // Tests random large complicated expressions, using all the possible
82 // operators, some literals, some parenthesized literals, and predefined
83 // character classes like \d. (Adding larger character classes would
84 // make for too many possibilities.)
TEST(Random,Complicated)85 TEST(Random, Complicated) {
86 std::vector<std::string> ops = Split(" ",
87 "%s%s %s|%s %s* %s*? %s+ %s+? %s? %s?? "
88 "%s{0} %s{0,} %s{1} %s{1,} %s{0,1} %s{0,2} %s{1,2} "
89 "%s{2} %s{2,} %s{3,4} %s{4,5}");
90
91 // Use (?:\b) and (?:\B) instead of \b and \B,
92 // because PCRE rejects \b* but accepts (?:\b)*.
93 // Ditto ^ and $.
94 std::vector<std::string> atoms = Split(" ",
95 ". (?:^) (?:$) \\a \\f \\n \\r \\t \\v "
96 "\\d \\D \\s \\S \\w \\W (?:\\b) (?:\\B) "
97 "a (a) b c - \\\\");
98 std::vector<std::string> alphabet = Explode("abc123\001\002\003\t\r\n\v\f\a");
99 RandomTest(10, 10, atoms, ops, 20, alphabet, "");
100 }
101
102 } // namespace re2
103