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