Replace uses of RE2 with Scanner, for sources that are used on mobile.

This CL also adds the Scanner class to do simple scans over strings, to mimic
regexp behavior like [a-zA-Z][a-zA-Z0-9]* with:

 Scanner scan(s);
 scan.One(Scanner::LETTER);
 scan.Any(Scanner::LETTER_DIGIT);
 bool matched = scan.GetResult();
Change: 116803757

3 files changed, 543 insertions, 0 deletions

diff --git a/tensorflow/core/lib/strings/scanner.cc b/tensorflow/core/lib/strings/scanner.cc
new file mode 100644
index 0000000000..b05400c97d
--- /dev/null
+++ b/tensorflow/core/lib/strings/scanner.cc
@@ -0,0 +1,59 @@
+/* Copyright 2016 Google Inc. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+
+#include "tensorflow/core/lib/strings/scanner.h"
+
+namespace tensorflow {
+namespace strings {
+
+void Scanner::ScanEscapedUntilImpl(char end_ch) {
+  for (;;) {
+    if (cur_.empty()) {
+      Error();
+      return;
+    }
+    const char ch = cur_[0];
+    if (ch == end_ch) {
+      return;
+    }
+
+    cur_.remove_prefix(1);
+    if (ch == '\\') {
+      // Escape character, skip next character.
+      if (cur_.empty()) {
+        Error();
+        return;
+      }
+      cur_.remove_prefix(1);
+    }
+  }
+}
+
+bool Scanner::GetResult(StringPiece* remaining, StringPiece* capture) {
+  if (error_) {
+    return false;
+  }
+  if (remaining != nullptr) {
+    *remaining = cur_;
+  }
+  if (capture != nullptr) {
+    const char* end = capture_end_ == nullptr ? cur_.data() : capture_end_;
+    *capture = StringPiece(capture_start_, end - capture_start_);
+  }
+  return true;
+}
+
+}  // namespace strings
+}  // namespace tensorflow
diff --git a/tensorflow/core/lib/strings/scanner.h b/tensorflow/core/lib/strings/scanner.h
new file mode 100644
index 0000000000..ecbb139d60
--- /dev/null
+++ b/tensorflow/core/lib/strings/scanner.h
@@ -0,0 +1,218 @@
+/* Copyright 2016 Google Inc. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+
+#ifndef TENSORFLOW_LIB_STRINGS_SCANNER_H_
+#define TENSORFLOW_LIB_STRINGS_SCANNER_H_
+
+#include <string>
+#include "tensorflow/core/lib/core/stringpiece.h"
+#include "tensorflow/core/platform/macros.h"
+
+namespace tensorflow {
+namespace strings {
+
+// Scanner provides simplified string parsing, in which a string is parsed as a
+// series of scanning calls (e.g. One, Any, Many, OneLiteral, Eos), and then
+// finally GetResult is called. If GetResult returns true, then it also returns
+// the remaining characters and any captured substring.
+//
+// The range to capture can be controlled with RestartCapture and StopCapture;
+// by default, all processed characters are captured.
+class Scanner {
+ public:
+  // Classes of characters. Each enum name is to be read as the union of the
+  // parts - e.g., class LETTER_DIGIT means the class includes all letters and
+  // all digits.
+  //
+  // LETTER means ascii letter a-zA-Z.
+  // DIGIT means ascii digit: 0-9.
+  enum CharClass {
+    // NOTE: When adding a new CharClass, update the AllCharClasses ScannerTest
+    // in scanner_test.cc
+    DIGIT,
+    LETTER,
+    LETTER_DIGIT,
+    LETTER_DIGIT_DASH_DOT_SLASH,             // SLASH is / only, not backslash
+    LETTER_DIGIT_DASH_DOT_SLASH_UNDERSCORE,  // SLASH is / only, not backslash
+    LETTER_DIGIT_DOT,
+    LETTER_DIGIT_DOT_UNDERSCORE,
+    LETTER_DIGIT_UNDERSCORE,
+    LOWERLETTER,
+    LOWERLETTER_DIGIT,
+    LOWERLETTER_DIGIT_UNDERSCORE,
+    NON_ZERO_DIGIT,
+    SPACE,
+    UPPERLETTER,
+  };
+
+  explicit Scanner(StringPiece source) : cur_(source) { RestartCapture(); }
+
+  // Consume the next character of the given class from input. If the next
+  // character is not in the class, then GetResult will ultimately return false.
+  Scanner& One(CharClass clz) {
+    if (cur_.empty() || !Matches(clz, cur_[0])) {
+      return Error();
+    }
+    cur_.remove_prefix(1);
+    return *this;
+  }
+
+  // Consume the next s.size() characters of the input, if they match <s>. If
+  // they don't match <s>, this is a no-op.
+  Scanner& ZeroOrOneLiteral(StringPiece s) {
+    cur_.Consume(s);
+    return *this;
+  }
+
+  // Consume the next s.size() characters of the input, if they match <s>. If
+  // they don't match <s>, then GetResult will ultimately return false.
+  Scanner& OneLiteral(StringPiece s) {
+    if (!cur_.Consume(s)) {
+      error_ = true;
+    }
+    return *this;
+  }
+
+  // Consume characters from the input as long as they match <clz>.
+  Scanner& Any(CharClass clz) {
+    while (!cur_.empty() && Matches(clz, cur_[0])) {
+      cur_.remove_prefix(1);
+    }
+    return *this;
+  }
+
+  // Shorthand for One(clz).Any(clz).
+  Scanner& Many(CharClass clz) { return One(clz).Any(clz); }
+
+  // Reset the capture start point.
+  //
+  // Later, when GetResult is called and if it returns true, the capture
+  // returned will start at the position at the time this was called.
+  Scanner& RestartCapture() {
+    capture_start_ = cur_.data();
+    return *this;
+  }
+
+  // Stop capturing input.
+  //
+  // Later, when GetResult is called and if it returns true, the capture
+  // returned will end at the position at the time this was called.
+  Scanner& StopCapture() {
+    capture_end_ = cur_.data();
+    return *this;
+  }
+
+  // If not at the input of input, then GetResult will ultimately return false.
+  Scanner& Eos() {
+    if (!cur_.empty()) error_ = true;
+    return *this;
+  }
+
+  // Shorthand for Any(SPACE).
+  Scanner& AnySpace() { return Any(SPACE); }
+
+  // This scans input until <end_ch> is reached. <end_ch> is NOT consumed.
+  // Backslash escape sequences are skipped.
+  // Used for implementing quoted string scanning.
+  Scanner& ScanEscapedUntil(char end_ch) {
+    ScanEscapedUntilImpl(end_ch);
+    return *this;
+  }
+
+  // Return the next character that will be scanned, or <default_value> if there
+  // are no more characters to scan.
+  // Note that if a scan operation has failed (so GetResult() returns false),
+  // then the value of Peek may or may not have advanced since the scan
+  // operation that failed.
+  char Peek(char default_value = '\0') const {
+    return cur_.empty() ? default_value : cur_[0];
+  }
+
+  // Returns true if the input string successfully matched. When true is
+  // returned, the remaining string is returned in <remaining> and the captured
+  // string returned in <capture>, if non-NULL.
+  bool GetResult(StringPiece* remaining = nullptr,
+                 StringPiece* capture = nullptr);
+
+ private:
+  void ScanEscapedUntilImpl(char end_ch);
+
+  Scanner& Error() {
+    error_ = true;
+    return *this;
+  }
+
+  static bool IsLetter(char ch) {
+    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
+  }
+
+  static bool IsLowerLetter(char ch) { return ch >= 'a' && ch <= 'z'; }
+
+  static bool IsDigit(char ch) { return ch >= '0' && ch <= '9'; }
+
+  static bool IsSpace(char ch) {
+    return (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\v' || ch == '\f' ||
+            ch == '\r');
+  }
+
+  static bool Matches(CharClass clz, char ch) {
+    switch (clz) {
+      case DIGIT:
+        return IsDigit(ch);
+      case LETTER:
+        return IsLetter(ch);
+      case LETTER_DIGIT:
+        return IsLetter(ch) || IsDigit(ch);
+      case LETTER_DIGIT_DASH_DOT_SLASH:
+        return IsLetter(ch) || IsDigit(ch) || ch == '-' || ch == '.' ||
+               ch == '/';
+      case LETTER_DIGIT_DASH_DOT_SLASH_UNDERSCORE:
+        return (IsLetter(ch) || IsDigit(ch) || ch == '-' || ch == '.' ||
+                ch == '/' || ch == '_');
+      case LETTER_DIGIT_DOT:
+        return IsLetter(ch) || IsDigit(ch) || ch == '.';
+      case LETTER_DIGIT_DOT_UNDERSCORE:
+        return IsLetter(ch) || IsDigit(ch) || ch == '.' || ch == '_';
+      case LETTER_DIGIT_UNDERSCORE:
+        return IsLetter(ch) || IsDigit(ch) || ch == '_';
+      case LOWERLETTER:
+        return ch >= 'a' && ch <= 'z';
+      case LOWERLETTER_DIGIT:
+        return IsLowerLetter(ch) || IsDigit(ch);
+      case LOWERLETTER_DIGIT_UNDERSCORE:
+        return IsLowerLetter(ch) || IsDigit(ch) || ch == '_';
+      case NON_ZERO_DIGIT:
+        return IsDigit(ch) && ch != '0';
+      case SPACE:
+        return IsSpace(ch);
+      case UPPERLETTER:
+        return ch >= 'A' && ch <= 'Z';
+    }
+    return false;
+  }
+
+  StringPiece cur_;
+  const char* capture_start_ = nullptr;
+  const char* capture_end_ = nullptr;
+  bool error_ = false;
+
+  friend class ScannerTest;
+  TF_DISALLOW_COPY_AND_ASSIGN(Scanner);
+};
+
+}  // namespace strings
+}  // namespace tensorflow
+
+#endif  // TENSORFLOW_LIB_STRINGS_SCANNER_H_
diff --git a/tensorflow/core/lib/strings/scanner_test.cc b/tensorflow/core/lib/strings/scanner_test.cc
new file mode 100644
index 0000000000..98028ae516
--- /dev/null
+++ b/tensorflow/core/lib/strings/scanner_test.cc
@@ -0,0 +1,266 @@
+/* Copyright 2016 Google Inc. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+
+#include "tensorflow/core/lib/strings/scanner.h"
+
+#include "tensorflow/core/platform/test.h"
+
+namespace tensorflow {
+namespace strings {
+
+class ScannerTest : public ::testing::Test {
+ protected:
+  // Returns a string with all chars that are in <clz>, in byte value order.
+  string ClassStr(Scanner::CharClass clz) {
+    string s;
+    for (int i = 0; i < 256; ++i) {
+      char ch = i;
+      if (Scanner::Matches(clz, ch)) {
+        s += ch;
+      }
+    }
+    return s;
+  }
+};
+
+TEST_F(ScannerTest, Any) {
+  StringPiece remaining, match;
+  EXPECT_TRUE(Scanner("   horse0123")
+                  .Any(Scanner::SPACE)
+                  .Any(Scanner::DIGIT)
+                  .Any(Scanner::LETTER)
+                  .GetResult(&remaining, &match));
+  EXPECT_EQ("   horse", match.ToString());
+  EXPECT_EQ("0123", remaining.ToString());
+
+  EXPECT_TRUE(Scanner("")
+                  .Any(Scanner::SPACE)
+                  .Any(Scanner::DIGIT)
+                  .Any(Scanner::LETTER)
+                  .GetResult(&remaining, &match));
+  EXPECT_EQ("", remaining.ToString());
+  EXPECT_EQ("", match.ToString());
+
+  EXPECT_TRUE(Scanner("----")
+                  .Any(Scanner::SPACE)
+                  .Any(Scanner::DIGIT)
+                  .Any(Scanner::LETTER)
+                  .GetResult(&remaining, &match));
+  EXPECT_EQ("----", remaining.ToString());
+  EXPECT_EQ("", match.ToString());
+}
+
+TEST_F(ScannerTest, AnySpace) {
+  StringPiece remaining, match;
+  EXPECT_TRUE(Scanner("  a b ")
+                  .AnySpace()
+                  .One(Scanner::LETTER)
+                  .AnySpace()
+                  .GetResult(&remaining, &match));
+  EXPECT_EQ("  a ", match.ToString());
+  EXPECT_EQ("b ", remaining.ToString());
+}
+
+TEST_F(ScannerTest, Eos) {
+  EXPECT_FALSE(Scanner("a").Eos().GetResult());
+  EXPECT_TRUE(Scanner("").Eos().GetResult());
+  EXPECT_FALSE(Scanner("abc").OneLiteral("ab").Eos().GetResult());
+  EXPECT_TRUE(Scanner("abc").OneLiteral("abc").Eos().GetResult());
+}
+
+TEST_F(ScannerTest, Many) {
+  StringPiece remaining, match;
+  EXPECT_TRUE(Scanner("abc").Many(Scanner::LETTER).GetResult());
+  EXPECT_FALSE(Scanner("0").Many(Scanner::LETTER).GetResult());
+  EXPECT_FALSE(Scanner("").Many(Scanner::LETTER).GetResult());
+
+  EXPECT_TRUE(
+      Scanner("abc ").Many(Scanner::LETTER).GetResult(&remaining, &match));
+  EXPECT_EQ(" ", remaining);
+  EXPECT_EQ("abc", match);
+  EXPECT_TRUE(
+      Scanner("abc").Many(Scanner::LETTER).GetResult(&remaining, &match));
+  EXPECT_EQ("", remaining);
+  EXPECT_EQ("abc", match);
+}
+
+TEST_F(ScannerTest, One) {
+  StringPiece remaining, match;
+  EXPECT_TRUE(Scanner("abc").One(Scanner::LETTER).GetResult());
+  EXPECT_FALSE(Scanner("0").One(Scanner::LETTER).GetResult());
+  EXPECT_FALSE(Scanner("").One(Scanner::LETTER).GetResult());
+
+  EXPECT_TRUE(Scanner("abc")
+                  .One(Scanner::LETTER)
+                  .One(Scanner::LETTER)
+                  .GetResult(&remaining, &match));
+  EXPECT_EQ("c", remaining);
+  EXPECT_EQ("ab", match);
+  EXPECT_TRUE(Scanner("a").One(Scanner::LETTER).GetResult(&remaining, &match));
+  EXPECT_EQ("", remaining);
+  EXPECT_EQ("a", match);
+}
+
+TEST_F(ScannerTest, OneLiteral) {
+  EXPECT_FALSE(Scanner("abc").OneLiteral("abC").GetResult());
+  EXPECT_TRUE(Scanner("abc").OneLiteral("ab").OneLiteral("c").GetResult());
+}
+
+TEST_F(ScannerTest, ScanEscapedUntil) {
+  StringPiece remaining, match;
+  EXPECT_TRUE(Scanner(R"(' \1 \2 \3 \' \\'rest)")
+                  .OneLiteral("'")
+                  .ScanEscapedUntil('\'')
+                  .OneLiteral("'")
+                  .GetResult(&remaining, &match));
+  EXPECT_EQ("rest", remaining.ToString());
+  EXPECT_EQ(R"(' \1 \2 \3 \' \\')", match.ToString());
+
+  // The "scan until" character is not present.
+  remaining = match = "unset";
+  EXPECT_FALSE(Scanner(R"(' \1 \2 \3 \' \\rest)")
+                   .OneLiteral("'")
+                   .ScanEscapedUntil('\'')
+                   .GetResult(&remaining, &match));
+  EXPECT_EQ("unset", remaining.ToString());
+  EXPECT_EQ("unset", match.ToString());
+}
+
+TEST_F(ScannerTest, ZeroOrOneLiteral) {
+  StringPiece remaining, match;
+  EXPECT_TRUE(
+      Scanner("abc").ZeroOrOneLiteral("abC").GetResult(&remaining, &match));
+  EXPECT_EQ("abc", remaining.ToString());
+  EXPECT_EQ("", match.ToString());
+
+  EXPECT_TRUE(
+      Scanner("abcd").ZeroOrOneLiteral("ab").ZeroOrOneLiteral("c").GetResult(
+          &remaining, &match));
+  EXPECT_EQ("d", remaining.ToString());
+  EXPECT_EQ("abc", match.ToString());
+
+  EXPECT_TRUE(
+      Scanner("").ZeroOrOneLiteral("abc").GetResult(&remaining, &match));
+  EXPECT_EQ("", remaining.ToString());
+  EXPECT_EQ("", match.ToString());
+}
+
+// Test output of GetResult (including the forms with optional params),
+// and that it can be called multiple times.
+TEST_F(ScannerTest, CaptureAndGetResult) {
+  StringPiece remaining, match;
+
+  Scanner scan("  first    second");
+  EXPECT_TRUE(scan.Any(Scanner::SPACE)
+                  .RestartCapture()
+                  .One(Scanner::LETTER)
+                  .Any(Scanner::LETTER_DIGIT)
+                  .StopCapture()
+                  .Any(Scanner::SPACE)
+                  .GetResult(&remaining, &match));
+  EXPECT_EQ("second", remaining.ToString());
+  EXPECT_EQ("first", match.ToString());
+  EXPECT_TRUE(scan.GetResult());
+  remaining = "";
+  EXPECT_TRUE(scan.GetResult(&remaining));
+  EXPECT_EQ("second", remaining.ToString());
+  remaining = "";
+  match = "";
+  EXPECT_TRUE(scan.GetResult(&remaining, &match));
+  EXPECT_EQ("second", remaining.ToString());
+  EXPECT_EQ("first", match.ToString());
+}
+
+// Tests that if StopCapture is not called, then calling GetResult, then
+// scanning more, then GetResult again will update the capture.
+TEST_F(ScannerTest, MultipleGetResultExtendsCapture) {
+  StringPiece remaining, match;
+
+  Scanner scan("one2three");
+  EXPECT_TRUE(scan.Many(Scanner::LETTER).GetResult(&remaining, &match));
+  EXPECT_EQ("2three", remaining.ToString());
+  EXPECT_EQ("one", match.ToString());
+  EXPECT_TRUE(scan.Many(Scanner::DIGIT).GetResult(&remaining, &match));
+  EXPECT_EQ("three", remaining.ToString());
+  EXPECT_EQ("one2", match.ToString());
+  EXPECT_TRUE(scan.Many(Scanner::LETTER).GetResult(&remaining, &match));
+  EXPECT_EQ("", remaining.ToString());
+  EXPECT_EQ("one2three", match.ToString());
+}
+
+TEST_F(ScannerTest, FailedMatchDoesntChangeResult) {
+  // A failed match doesn't change pointers passed to GetResult.
+  Scanner scan("name");
+  StringPiece remaining = "rem";
+  StringPiece match = "match";
+  EXPECT_FALSE(scan.One(Scanner::SPACE).GetResult(&remaining, &match));
+  EXPECT_EQ("rem", remaining.ToString());
+  EXPECT_EQ("match", match.ToString());
+}
+
+TEST_F(ScannerTest, DefaultCapturesAll) {
+  // If RestartCapture() is not called, the whole string is used.
+  Scanner scan("a b");
+  StringPiece remaining = "rem";
+  StringPiece match = "match";
+  EXPECT_TRUE(scan.Any(Scanner::LETTER)
+                  .AnySpace()
+                  .Any(Scanner::LETTER)
+                  .GetResult(&remaining, &match));
+  EXPECT_EQ("", remaining.ToString());
+  EXPECT_EQ("a b", match.ToString());
+}
+
+TEST_F(ScannerTest, AllCharClasses) {
+  EXPECT_EQ("0123456789", ClassStr(Scanner::DIGIT));
+  EXPECT_EQ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",
+            ClassStr(Scanner::LETTER));
+  EXPECT_EQ("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",
+            ClassStr(Scanner::LETTER_DIGIT));
+  EXPECT_EQ(
+      "-./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+      "abcdefghijklmnopqrstuvwxyz",
+      ClassStr(Scanner::LETTER_DIGIT_DASH_DOT_SLASH));
+  EXPECT_EQ(
+      "-./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_"
+      "abcdefghijklmnopqrstuvwxyz",
+      ClassStr(Scanner::LETTER_DIGIT_DASH_DOT_SLASH_UNDERSCORE));
+  EXPECT_EQ(".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",
+            ClassStr(Scanner::LETTER_DIGIT_DOT));
+  EXPECT_EQ(".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz",
+            ClassStr(Scanner::LETTER_DIGIT_DOT_UNDERSCORE));
+  EXPECT_EQ("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz",
+            ClassStr(Scanner::LETTER_DIGIT_UNDERSCORE));
+  EXPECT_EQ("abcdefghijklmnopqrstuvwxyz", ClassStr(Scanner::LOWERLETTER));
+  EXPECT_EQ("0123456789abcdefghijklmnopqrstuvwxyz",
+            ClassStr(Scanner::LOWERLETTER_DIGIT));
+  EXPECT_EQ("0123456789_abcdefghijklmnopqrstuvwxyz",
+            ClassStr(Scanner::LOWERLETTER_DIGIT_UNDERSCORE));
+  EXPECT_EQ("123456789", ClassStr(Scanner::NON_ZERO_DIGIT));
+  EXPECT_EQ("\t\n\v\f\r ", ClassStr(Scanner::SPACE));
+  EXPECT_EQ("ABCDEFGHIJKLMNOPQRSTUVWXYZ", ClassStr(Scanner::UPPERLETTER));
+}
+
+TEST_F(ScannerTest, Peek) {
+  EXPECT_EQ('a', Scanner("abc").Peek());
+  EXPECT_EQ('a', Scanner("abc").Peek('b'));
+  EXPECT_EQ('\0', Scanner("").Peek());
+  EXPECT_EQ('z', Scanner("").Peek('z'));
+  EXPECT_EQ('A', Scanner("0123A").Any(Scanner::DIGIT).Peek());
+  EXPECT_EQ('\0', Scanner("0123A").Any(Scanner::LETTER_DIGIT).Peek());
+}
+
+}  // namespace strings
+}  // namespace tensorflow