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
18namespace re2 {
19
20StringGenerator::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.
35void 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.
45bool 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.
64bool 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.
84const 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.
101void StringGenerator::Random(int32_t seed, int n) {
102 rng_.seed(seed);
103
104 random_ = true;
105 nrandom_ = n;
106 hasnext_ = nrandom_ > 0;
107}
108
109void StringGenerator::GenerateNULL() {
110 generate_null_ = true;
111 hasnext_ = true;
112}
113
114} // namespace re2
115