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