15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2008 The RE2 Authors. All Rights Reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// license that can be found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Test StringGenerator. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdlib.h> 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/test.h" 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "re2/testing/string_generator.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "re2/testing/regexp_generator.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace re2 { 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns i to the e. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int64 IntegerPower(int i, int e) { 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 p = 1; 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (e-- > 0) 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p *= i; 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Checks that for given settings of the string generator: 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * it generates strings that are non-decreasing in length. 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * strings of the same length are sorted in alphabet order. 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * it doesn't generate the same string twice. 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * it generates the right number of strings. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If all of these hold, the StringGenerator is behaving. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Assumes that the alphabet is sorted, so that the generated 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// strings can just be compared lexicographically. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void RunTest(int len, string alphabet, bool donull) { 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringGenerator g(len, Explode(alphabet)); 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n = 0; 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int last_l = -1; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) string last_s; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (donull) { 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) g.GenerateNULL(); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(g.HasNext()); 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StringPiece sp = g.Next(); 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(sp.data(), static_cast<const char*>(NULL)); 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(sp.size(), 0); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (g.HasNext()) { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) string s = g.Next().as_string(); 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n++; 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check that all characters in s appear in alphabet. 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (const char *p = s.c_str(); *p != '\0'; ) { 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Rune r; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p += chartorune(&r, p); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_TRUE(utfrune(alphabet.c_str(), r) != NULL); 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check that string is properly ordered w.r.t. previous string. 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int l = utflen(s.c_str()); 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_LE(l, len); 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last_l < l) { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_l = l; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(last_l, l); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_LT(last_s, s); 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_s = s; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check total string count. 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 m = 0; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int alpha = utflen(alphabet.c_str()); 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (alpha == 0) // Degenerate case. 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) len = 0; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i <= len; i++) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) m += IntegerPower(alpha, i); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(n, m); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(StringGenerator, NoLength) { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(0, "abc", false); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(StringGenerator, NoLengthNoAlphabet) { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(0, "", false); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(StringGenerator, NoAlphabet) { 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(5, "", false); 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(StringGenerator, Simple) { 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(3, "abc", false); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(StringGenerator, UTF8) { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(4, "abc\xE2\x98\xBA", false); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(StringGenerator, GenNULL) { 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(0, "abc", true); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(0, "", true); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(5, "", true); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(3, "abc", true); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RunTest(4, "abc\xE2\x98\xBA", true); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace re2 110