10d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Copyright 2008 The RE2 Authors. All Rights Reserved. 20d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Use of this source code is governed by a BSD-style 30d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// license that can be found in the LICENSE file. 40d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 50d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Test StringGenerator. 60d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 70d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include <stdlib.h> 80d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include <string> 90d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include <vector> 100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "util/test.h" 110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "re2/testing/string_generator.h" 120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "re2/testing/regexp_generator.h" 130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinnamespace re2 { 150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Returns i to the e. 170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinstatic int64 IntegerPower(int i, int e) { 180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin int64 p = 1; 190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin while (e-- > 0) 200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin p *= i; 210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin return p; 220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} 230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Checks that for given settings of the string generator: 250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// * it generates strings that are non-decreasing in length. 260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// * strings of the same length are sorted in alphabet order. 270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// * it doesn't generate the same string twice. 280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// * it generates the right number of strings. 290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// 300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// If all of these hold, the StringGenerator is behaving. 310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Assumes that the alphabet is sorted, so that the generated 320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// strings can just be compared lexicographically. 330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinstatic void RunTest(int len, string alphabet, bool donull) { 340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin StringGenerator g(len, Explode(alphabet)); 350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin int n = 0; 370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin int last_l = -1; 380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin string last_s; 390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin if (donull) { 410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin g.GenerateNULL(); 420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin EXPECT_TRUE(g.HasNext()); 430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin StringPiece sp = g.Next(); 440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin EXPECT_EQ(sp.data(), static_cast<const char*>(NULL)); 450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin EXPECT_EQ(sp.size(), 0); 460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin } 470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin while (g.HasNext()) { 490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin string s = g.Next().as_string(); 500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin n++; 510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin // Check that all characters in s appear in alphabet. 530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin for (const char *p = s.c_str(); *p != '\0'; ) { 540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin Rune r; 550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin p += chartorune(&r, p); 560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin EXPECT_TRUE(utfrune(alphabet.c_str(), r) != NULL); 570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin } 580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin // Check that string is properly ordered w.r.t. previous string. 600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin int l = utflen(s.c_str()); 610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin EXPECT_LE(l, len); 620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin if (last_l < l) { 630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin last_l = l; 640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin } else { 650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin EXPECT_EQ(last_l, l); 660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin EXPECT_LT(last_s, s); 670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin } 680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin last_s = s; 690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin } 700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin // Check total string count. 720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin int64 m = 0; 730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin int alpha = utflen(alphabet.c_str()); 740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin if (alpha == 0) // Degenerate case. 750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin len = 0; 760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin for (int i = 0; i <= len; i++) 770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin m += IntegerPower(alpha, i); 780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin EXPECT_EQ(n, m); 790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} 800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinTEST(StringGenerator, NoLength) { 820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(0, "abc", false); 830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} 840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinTEST(StringGenerator, NoLengthNoAlphabet) { 860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(0, "", false); 870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} 880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinTEST(StringGenerator, NoAlphabet) { 900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(5, "", false); 910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} 920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinTEST(StringGenerator, Simple) { 940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(3, "abc", false); 950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} 960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinTEST(StringGenerator, UTF8) { 980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(4, "abc\xE2\x98\xBA", false); 990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} 1000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 1010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinTEST(StringGenerator, GenNULL) { 1020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(0, "abc", true); 1030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(0, "", true); 1040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(5, "", true); 1050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(3, "abc", true); 1060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin RunTest(4, "abc\xE2\x98\xBA", true); 1070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} 1080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin 1090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin} // namespace re2 110