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 // String generator: generates all possible strings of up to
6 // maxlen letters using the set of letters in alpha.
7 // Fetch strings using a Java-like Next()/HasNext() interface.
8
9 #include <stddef.h>
10 #include <stdint.h>
11 #include <string>
12 #include <vector>
13
14 #include "util/test.h"
15 #include "util/logging.h"
16 #include "re2/testing/string_generator.h"
17
18 namespace re2 {
19
StringGenerator(int maxlen,const std::vector<std::string> & alphabet)20 StringGenerator::StringGenerator(int maxlen,
21 const std::vector<std::string>& alphabet)
22 : maxlen_(maxlen), alphabet_(alphabet),
23 generate_null_(false),
24 random_(false), nrandom_(0) {
25
26 // Degenerate case: no letters, no non-empty strings.
27 if (alphabet_.empty())
28 maxlen_ = 0;
29
30 // Next() will return empty string (digits_ is empty).
31 hasnext_ = true;
32 }
33
34 // Resets the string generator state to the beginning.
Reset()35 void StringGenerator::Reset() {
36 digits_.clear();
37 hasnext_ = true;
38 random_ = false;
39 nrandom_ = 0;
40 generate_null_ = false;
41 }
42
43 // Increments the big number in digits_, returning true if successful.
44 // Returns false if all the numbers have been used.
IncrementDigits()45 bool StringGenerator::IncrementDigits() {
46 // First try to increment the current number.
47 for (int i = static_cast<int>(digits_.size()) - 1; i >= 0; i--) {
48 if (++digits_[i] < static_cast<int>(alphabet_.size()))
49 return true;
50 digits_[i] = 0;
51 }
52
53 // If that failed, make a longer number.
54 if (static_cast<int>(digits_.size()) < maxlen_) {
55 digits_.push_back(0);
56 return true;
57 }
58
59 return false;
60 }
61
62 // Generates random digits_, return true if successful.
63 // Returns false if the random sequence is over.
RandomDigits()64 bool StringGenerator::RandomDigits() {
65 if (--nrandom_ <= 0)
66 return false;
67
68 std::uniform_int_distribution<int> random_len(0, maxlen_);
69 std::uniform_int_distribution<int> random_alphabet_index(
70 0, static_cast<int>(alphabet_.size()) - 1);
71
72 // Pick length.
73 int len = random_len(rng_);
74 digits_.resize(len);
75 for (int i = 0; i < len; i++)
76 digits_[i] = random_alphabet_index(rng_);
77 return true;
78 }
79
80 // Returns the next string in the iteration, which is the one
81 // currently described by digits_. Calls IncrementDigits
82 // after computing the string, so that it knows the answer
83 // for subsequent HasNext() calls.
Next()84 const StringPiece& StringGenerator::Next() {
85 CHECK(hasnext_);
86 if (generate_null_) {
87 generate_null_ = false;
88 sp_ = StringPiece();
89 return sp_;
90 }
91 s_.clear();
92 for (size_t i = 0; i < digits_.size(); i++) {
93 s_ += alphabet_[digits_[i]];
94 }
95 hasnext_ = random_ ? RandomDigits() : IncrementDigits();
96 sp_ = s_;
97 return sp_;
98 }
99
100 // Sets generator up to return n random strings.
Random(int32_t seed,int n)101 void StringGenerator::Random(int32_t seed, int n) {
102 rng_.seed(seed);
103
104 random_ = true;
105 nrandom_ = n;
106 hasnext_ = nrandom_ > 0;
107 }
108
GenerateNULL()109 void StringGenerator::GenerateNULL() {
110 generate_null_ = true;
111 hasnext_ = true;
112 }
113
DeBruijnString(int n)114 std::string DeBruijnString(int n) {
115 CHECK_GE(n, 1);
116 CHECK_LE(n, 29);
117 const size_t size = size_t{1} << static_cast<size_t>(n);
118 const size_t mask = size - 1;
119 std::vector<bool> did(size, false);
120 std::string s;
121 s.reserve(static_cast<size_t>(n) + size);
122 for (size_t i = 0; i < static_cast<size_t>(n - 1); i++)
123 s += '0';
124 size_t bits = 0;
125 for (size_t i = 0; i < size; i++) {
126 bits <<= 1;
127 bits &= mask;
128 if (!did[bits | 1]) {
129 bits |= 1;
130 s += '1';
131 } else {
132 s += '0';
133 }
134 CHECK(!did[bits]);
135 did[bits] = true;
136 }
137 CHECK_EQ(s.size(), static_cast<size_t>(n - 1) + size);
138 return s;
139 }
140
141 } // namespace re2
142