normalize string_util (#708)

* refactoring string_util
* port string_util to iOS

3 files changed, 127 insertions, 0 deletions

diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
index 09db164..51621a0 100644
--- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
+++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
@@ -113,6 +113,8 @@ cc_library(
     firebase_assert.h
     log.h
     secure_random.h
+    string_util.cc
+    string_util.h
   DEPENDS
     ${UTIL_DEPENDS}
     firebase_firestore_util_base
diff --git a/Firestore/core/src/firebase/firestore/util/string_util.cc b/Firestore/core/src/firebase/firestore/util/string_util.cc
new file mode 100644
index 0000000..b7f1ed9
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/string_util.cc
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2017 Google
+ *
+ * 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 "Firestore/core/src/firebase/firestore/util/string_util.h"
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+std::string PrefixSuccessor(absl::string_view prefix) {
+  // We can increment the last character in the string and be done
+  // unless that character is 255 (0xff), in which case we have to erase the
+  // last character and increment the previous character, unless that
+  // is 255, etc. If the string is empty or consists entirely of
+  // 255's, we just return the empty string.
+  std::string limit(prefix);
+  while (!limit.empty()) {
+    size_t index = limit.length() - 1;
+    if (limit[index] == '\xff') {  // char literal avoids signed/unsigned.
+      limit.erase(index);
+    } else {
+      limit[index]++;
+      break;
+    }
+  }
+  return limit;
+}
+
+std::string ImmediateSuccessor(absl::string_view s) {
+  // Return the input string, with an additional NUL byte appended.
+  std::string out;
+  out.reserve(s.size() + 1);
+  out.append(s.data(), s.size());
+  out.push_back('\0');
+  return out;
+}
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
diff --git a/Firestore/core/src/firebase/firestore/util/string_util.h b/Firestore/core/src/firebase/firestore/util/string_util.h
new file mode 100644
index 0000000..3de177d
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/string_util.h
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2017 Google
+ *
+ * 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.
+ */
+
+// Useful string functions and so forth.  This is a grab-bag file.
+//
+// These functions work fine for UTF-8 strings as long as you can
+// consider them to be just byte strings.  For example, due to the
+// design of UTF-8 you do not need to worry about accidental matches,
+// as long as all your inputs are valid UTF-8 (use \uHHHH, not \xHH or \oOOO).
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_UTIL_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_UTIL_H_
+
+#include <string>
+
+#include "absl/strings/string_view.h"
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+/*
+ * Returns the smallest lexicographically larger string of equal or smaller
+ * length. Returns an empty string if there is no such successor (if the input
+ * is empty or consists entirely of 0xff bytes).
+ * Useful for calculating the smallest lexicographically larger string
+ * that will not be prefixed by the input string.
+ *
+ * Examples:
+ * "a" -> "b", "aaa" -> "aab", "aa\xff" -> "ab", "\xff" -> "", "" -> ""
+ */
+std::string PrefixSuccessor(absl::string_view prefix);
+
+/*
+ * Returns the immediate lexicographically-following string. This is useful to
+ * turn an inclusive range into something that can be used with Bigtable's
+ * SetLimitRow():
+ *
+ *     // Inclusive range [min_element, max_element].
+ *     string min_element = ...;
+ *     string max_element = ...;
+ *
+ *     // Equivalent range [range_start, range_end).
+ *     string range_start = min_element;
+ *     string range_end = ImmediateSuccessor(max_element);
+ *
+ * WARNING: Returns the input string with a '\0' appended; if you call c_str()
+ * on the result, it will compare equal to s.
+ *
+ * WARNING: Transforms "" -> "\0"; this doesn't account for Bigtable's special
+ * treatment of "" as infinity.
+ */
+std::string ImmediateSuccessor(absl::string_view s);
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_UTIL_H_