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 | // Test StringGenerator. |
6 | |
7 | #include <stdint.h> |
8 | #include <string> |
9 | |
10 | #include "util/test.h" |
11 | #include "util/utf.h" |
12 | #include "re2/testing/string_generator.h" |
13 | #include "re2/testing/regexp_generator.h" |
14 | |
15 | namespace re2 { |
16 | |
17 | // Returns i to the e. |
18 | static int64_t IntegerPower(int i, int e) { |
19 | int64_t p = 1; |
20 | while (e-- > 0) |
21 | p *= i; |
22 | return p; |
23 | } |
24 | |
25 | // Checks that for given settings of the string generator: |
26 | // * it generates strings that are non-decreasing in length. |
27 | // * strings of the same length are sorted in alphabet order. |
28 | // * it doesn't generate the same string twice. |
29 | // * it generates the right number of strings. |
30 | // |
31 | // If all of these hold, the StringGenerator is behaving. |
32 | // Assumes that the alphabet is sorted, so that the generated |
33 | // strings can just be compared lexicographically. |
34 | static void RunTest(int len, const std::string& alphabet, bool donull) { |
35 | StringGenerator g(len, Explode(alphabet)); |
36 | |
37 | int n = 0; |
38 | int last_l = -1; |
39 | std::string last_s; |
40 | |
41 | if (donull) { |
42 | g.GenerateNULL(); |
43 | EXPECT_TRUE(g.HasNext()); |
44 | StringPiece sp = g.Next(); |
45 | EXPECT_EQ(sp.data(), static_cast<const char*>(NULL)); |
46 | EXPECT_EQ(sp.size(), 0); |
47 | } |
48 | |
49 | while (g.HasNext()) { |
50 | std::string s = std::string(g.Next()); |
51 | n++; |
52 | |
53 | // Check that all characters in s appear in alphabet. |
54 | for (const char *p = s.c_str(); *p != '\0'; ) { |
55 | Rune r; |
56 | p += chartorune(&r, p); |
57 | EXPECT_TRUE(utfrune(alphabet.c_str(), r) != NULL); |
58 | } |
59 | |
60 | // Check that string is properly ordered w.r.t. previous string. |
61 | int l = utflen(s.c_str()); |
62 | EXPECT_LE(l, len); |
63 | if (last_l < l) { |
64 | last_l = l; |
65 | } else { |
66 | EXPECT_EQ(last_l, l); |
67 | EXPECT_LT(last_s, s); |
68 | } |
69 | last_s = s; |
70 | } |
71 | |
72 | // Check total string count. |
73 | int64_t m = 0; |
74 | int alpha = utflen(alphabet.c_str()); |
75 | if (alpha == 0) // Degenerate case. |
76 | len = 0; |
77 | for (int i = 0; i <= len; i++) |
78 | m += IntegerPower(alpha, i); |
79 | EXPECT_EQ(n, m); |
80 | } |
81 | |
82 | TEST(StringGenerator, NoLength) { |
83 | RunTest(0, "abc" , false); |
84 | } |
85 | |
86 | TEST(StringGenerator, NoLengthNoAlphabet) { |
87 | RunTest(0, "" , false); |
88 | } |
89 | |
90 | TEST(StringGenerator, NoAlphabet) { |
91 | RunTest(5, "" , false); |
92 | } |
93 | |
94 | TEST(StringGenerator, Simple) { |
95 | RunTest(3, "abc" , false); |
96 | } |
97 | |
98 | TEST(StringGenerator, UTF8) { |
99 | RunTest(4, "abc\xE2\x98\xBA" , false); |
100 | } |
101 | |
102 | TEST(StringGenerator, GenNULL) { |
103 | RunTest(0, "abc" , true); |
104 | RunTest(0, "" , true); |
105 | RunTest(5, "" , true); |
106 | RunTest(3, "abc" , true); |
107 | RunTest(4, "abc\xE2\x98\xBA" , true); |
108 | } |
109 | |
110 | } // namespace re2 |
111 | |