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