src/third_party/re2/re2/testing/string_generator_test.cc

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