Home | History | Annotate | Download | only in testing 
      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 
     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 
     29 StringGenerator::~StringGenerator() {
     30   delete acm_;
     31 }
     32 
     33 // Resets the string generator state to the beginning.
     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.
     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.
     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.
     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.
     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 
    107 void StringGenerator::GenerateNULL() {
    108   generate_null_ = true;
    109   hasnext_ = true;
    110 }
    111 
    112 }  // namespace re2
    113 
    114