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
15namespace re2 {
16
17// Returns i to the e.
18static 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.
34static 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
82TEST(StringGenerator, NoLength) {
83 RunTest(0, "abc", false);
84}
85
86TEST(StringGenerator, NoLengthNoAlphabet) {
87 RunTest(0, "", false);
88}
89
90TEST(StringGenerator, NoAlphabet) {
91 RunTest(5, "", false);
92}
93
94TEST(StringGenerator, Simple) {
95 RunTest(3, "abc", false);
96}
97
98TEST(StringGenerator, UTF8) {
99 RunTest(4, "abc\xE2\x98\xBA", false);
100}
101
102TEST(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