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 <string>
10 #include <vector>
11 #include "util/test.h"
12 #include "re2/testing/string_generator.h"
13
14 namespace re2 {
15
StringGenerator(int maxlen,const vector<string> & alphabet)16 StringGenerator::StringGenerator(int maxlen, const vector<string>& alphabet)
17 : maxlen_(maxlen), alphabet_(alphabet),
18 generate_null_(false),
19 random_(false), nrandom_(0), acm_(NULL) {
20
21 // Degenerate case: no letters, no non-empty strings.
22 if (alphabet_.size() == 0)
23 maxlen_ = 0;
24
25 // Next() will return empty string (digits_ is empty).
26 hasnext_ = true;
27 }
28
~StringGenerator()29 StringGenerator::~StringGenerator() {
30 delete acm_;
31 }
32
33 // Resets the string generator state to the beginning.
Reset()34 void StringGenerator::Reset() {
35 digits_.clear();
36 hasnext_ = true;
37 random_ = false;
38 nrandom_ = 0;
39 generate_null_ = false;
40 }
41
42 // Increments the big number in digits_, returning true if successful.
43 // Returns false if all the numbers have been used.
IncrementDigits()44 bool StringGenerator::IncrementDigits() {
45 // First try to increment the current number.
46 for (int i = digits_.size() - 1; i >= 0; i--) {
47 if (++digits_[i] < alphabet_.size())
48 return true;
49 digits_[i] = 0;
50 }
51
52 // If that failed, make a longer number.
53 if (digits_.size() < maxlen_) {
54 digits_.push_back(0);
55 return true;
56 }
57
58 return false;
59 }
60
61 // Generates random digits_, return true if successful.
62 // Returns false if the random sequence is over.
RandomDigits()63 bool StringGenerator::RandomDigits() {
64 if (--nrandom_ <= 0)
65 return false;
66
67 // Pick length.
68 int len = acm_->Uniform(maxlen_+1);
69 digits_.resize(len);
70 for (int i = 0; i < len; i++)
71 digits_[i] = acm_->Uniform(alphabet_.size());
72 return true;
73 }
74
75 // Returns the next string in the iteration, which is the one
76 // currently described by digits_. Calls IncrementDigits
77 // after computing the string, so that it knows the answer
78 // for subsequent HasNext() calls.
Next()79 const StringPiece& StringGenerator::Next() {
80 CHECK(hasnext_);
81 if (generate_null_) {
82 generate_null_ = false;
83 sp_ = NULL;
84 return sp_;
85 }
86 s_.clear();
87 for (int i = 0; i < digits_.size(); i++) {
88 s_ += alphabet_[digits_[i]];
89 }
90 hasnext_ = random_ ? RandomDigits() : IncrementDigits();
91 sp_ = s_;
92 return sp_;
93 }
94
95 // Sets generator up to return n random strings.
Random(int32 seed,int n)96 void StringGenerator::Random(int32 seed, int n) {
97 if (acm_ == NULL)
98 acm_ = new ACMRandom(seed);
99 else
100 acm_->Reset(seed);
101
102 random_ = true;
103 nrandom_ = n;
104 hasnext_ = nrandom_ > 0;
105 }
106
GenerateNULL()107 void StringGenerator::GenerateNULL() {
108 generate_null_ = true;
109 hasnext_ = true;
110 }
111
112 } // namespace re2
113
114