string_generator_test.cc revision 5821806d5e7f356e8fa4b058a389a808ea183019 
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