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