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