Include RE2 library

third_party/re2/re2/testing/string_generator.cc

Index: third_party/re2/re2/testing/string_generator.cc
diff --git a/third_party/re2/re2/testing/string_generator.cc b/third_party/re2/re2/testing/string_generator.cc
new file mode 100644
index 0000000000000000000000000000000000000000..5be6d3eb5d9002c9518199e02aba628a6915164c
--- /dev/null
+++ b/third_party/re2/re2/testing/string_generator.cc
@@ -0,0 +1,113 @@
+// Copyright 2008 The RE2 Authors.  All Rights Reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// String generator: generates all possible strings of up to
+// maxlen letters using the set of letters in alpha.
+// Fetch strings using a Java-like Next()/HasNext() interface.
+
+#include <string>
+#include <vector>
+#include "util/test.h"
+#include "re2/testing/string_generator.h"
+
+namespace re2 {
+
+StringGenerator::StringGenerator(int maxlen, const vector<string>& alphabet)
+    : maxlen_(maxlen), alphabet_(alphabet),
+      generate_null_(false),
+      random_(false), nrandom_(0), acm_(NULL) {
+
+  // Degenerate case: no letters, no non-empty strings.
+  if (alphabet_.size() == 0)
+    maxlen_ = 0;
+
+  // Next() will return empty string (digits_ is empty).
+  hasnext_ = true;
+}
+
+StringGenerator::~StringGenerator() {
+  delete acm_;
+}
+
+// Resets the string generator state to the beginning.
+void StringGenerator::Reset() {
+  digits_.clear();
+  hasnext_ = true;
+  random_ = false;
+  nrandom_ = 0;
+  generate_null_ = false;
+}
+
+// Increments the big number in digits_, returning true if successful.
+// Returns false if all the numbers have been used.
+bool StringGenerator::IncrementDigits() {
+  // First try to increment the current number.
+  for (int i = digits_.size() - 1; i >= 0; i--) {
+    if (++digits_[i] < alphabet_.size())
+      return true;
+    digits_[i] = 0;
+  }
+
+  // If that failed, make a longer number.
+  if (digits_.size() < maxlen_) {
+    digits_.push_back(0);
+    return true;
+  }
+
+  return false;
+}
+
+// Generates random digits_, return true if successful.
+// Returns false if the random sequence is over.
+bool StringGenerator::RandomDigits() {
+  if (--nrandom_ <= 0)
+    return false;
+
+  // Pick length.
+  int len = acm_->Uniform(maxlen_+1);
+  digits_.resize(len);
+  for (int i = 0; i < len; i++)
+    digits_[i] = acm_->Uniform(alphabet_.size());
+  return true;
+}
+
+// Returns the next string in the iteration, which is the one
+// currently described by digits_.  Calls IncrementDigits
+// after computing the string, so that it knows the answer
+// for subsequent HasNext() calls.
+const StringPiece& StringGenerator::Next() {
+  CHECK(hasnext_);
+  if (generate_null_) {
+    generate_null_ = false;
+    sp_ = NULL;
+    return sp_;
+  }
+  s_.clear();
+  for (int i = 0; i < digits_.size(); i++) {
+    s_ += alphabet_[digits_[i]];
+  }
+  hasnext_ = random_ ? RandomDigits() : IncrementDigits();
+  sp_ = s_;
+  return sp_;
+}
+
+// Sets generator up to return n random strings.
+void StringGenerator::Random(int32 seed, int n) {
+  if (acm_ == NULL)
+    acm_ = new ACMRandom(seed);
+  else
+    acm_->Reset(seed);
+
+  random_ = true;
+  nrandom_ = n;
+  hasnext_ = nrandom_ > 0;
+}
+
+void StringGenerator::GenerateNULL() {
+  generate_null_ = true;
+  hasnext_ = true;
+}
+
+}  // namespace re2
+