Port comparison to C++ (#678)

This reimplements our comparison functions as C++ Comparators and then provides compatibility shims for interoperating with existing Objective-C usage.

A few specialized comparators aren't suitable for porting but only have a single usage (e.g. CompareBytes for comparing NSData * instances). In these cases I've moved them into the caller.

* Use int32_t for typeof(ID) in FSTDocumentReference

* Migrate callers of FSTComparison.h to Objective-C++

* Port comparison to C++

* Migrate usages of FSTComparison.h to C++ equivalents

* Remove FSTComparison

4 files changed, 309 insertions, 0 deletions

diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
index 737173b..09db164 100644
--- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
+++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
@@ -49,6 +49,7 @@ cc_library(
     string_apple.h
   DEPENDS
     FirebaseCore
+    absl_strings
   EXCLUDE_FROM_ALL
 )
 
@@ -106,6 +107,8 @@ cc_library(
   SOURCES
     autoid.cc
     autoid.h
+    comparison.cc
+    comparison.h
     config.h
     firebase_assert.h
     log.h
diff --git a/Firestore/core/src/firebase/firestore/util/comparison.cc b/Firestore/core/src/firebase/firestore/util/comparison.cc
new file mode 100644
index 0000000..4bef843
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/comparison.cc
@@ -0,0 +1,112 @@
+/*
+ * Copyright 2018 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/comparison.h"
+
+#include <math.h>
+
+#include <limits>
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+bool Comparator<absl::string_view>::operator()(
+    const absl::string_view& left, const absl::string_view& right) const {
+  // TODO(wilhuff): truncation aware comparison
+  return left < right;
+}
+
+bool Comparator<double>::operator()(double left, double right) const {
+  // NaN sorts equal to itself and before any other number.
+  if (left < right) {
+    return true;
+  } else if (left >= right) {
+    return false;
+  } else {
+    // One or both left and right is NaN.
+    return isnan(left) && !isnan(right);
+  }
+}
+
+static constexpr double INT64_MIN_VALUE_AS_DOUBLE =
+    static_cast<double>(std::numeric_limits<int64_t>::min());
+
+static constexpr double INT64_MAX_VALUE_AS_DOUBLE =
+    static_cast<double>(std::numeric_limits<int64_t>::max());
+
+ComparisonResult CompareMixedNumber(double double_value, int64_t int64_value) {
+  // LLONG_MIN has an exact representation as double, so to check for a value
+  // outside the range representable by long, we have to check for strictly less
+  // than LLONG_MIN. Note that this also handles negative infinity.
+  if (double_value < INT64_MIN_VALUE_AS_DOUBLE) {
+    return ComparisonResult::Ascending;
+  }
+
+  // LLONG_MAX has no exact representation as double (casting as we've done
+  // makes 2^63, which is larger than LLONG_MAX), so consider any value greater
+  // than or equal to the threshold to be out of range. This also handles
+  // positive infinity.
+  if (double_value >= INT64_MAX_VALUE_AS_DOUBLE) {
+    return ComparisonResult::Descending;
+  }
+
+  // In Firestore NaN is defined to compare before all other numbers.
+  if (isnan(double_value)) {
+    return ComparisonResult::Ascending;
+  }
+
+  auto double_as_int64 = static_cast<int64_t>(double_value);
+  ComparisonResult cmp = Compare<int64_t>(double_as_int64, int64_value);
+  if (cmp != ComparisonResult::Same) {
+    return cmp;
+  }
+
+  // At this point the long representations are equal but this could be due to
+  // rounding.
+  double int64_as_double = static_cast<double>(int64_value);
+  return Compare<double>(double_value, int64_as_double);
+}
+
+/** Helper to normalize a double and then return the raw bits as a uint64_t. */
+uint64_t DoubleBits(double d) {
+  if (isnan(d)) {
+    d = NAN;
+  }
+
+  // Unlike C, C++ does not define type punning through a union type.
+
+  // TODO(wilhuff): replace with absl::bit_cast
+  static_assert(sizeof(double) == sizeof(uint64_t), "doubles must be 8 bytes");
+  uint64_t bits;
+  memcpy(&bits, &d, sizeof(bits));
+  return bits;
+}
+
+bool DoubleBitwiseEquals(double left, double right) {
+  return DoubleBits(left) == DoubleBits(right);
+}
+
+size_t DoubleBitwiseHash(double d) {
+  uint64_t bits = DoubleBits(d);
+  // Note that x ^ (x >> 32) works fine for both 32 and 64 bit definitions of
+  // size_t
+  return static_cast<size_t>(bits) ^ static_cast<size_t>(bits >> 32);
+}
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
diff --git a/Firestore/core/src/firebase/firestore/util/comparison.h b/Firestore/core/src/firebase/firestore/util/comparison.h
new file mode 100644
index 0000000..6fd1e2b
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/comparison.h
@@ -0,0 +1,181 @@
+/*
+ * Copyright 2018 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.
+ */
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_COMPARISON_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_COMPARISON_H_
+
+#if __OBJC__
+#import <Foundation/Foundation.h>
+#endif
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <functional>
+#include <string>
+#include <vector>
+
+#include "Firestore/core/src/firebase/firestore/util/string_apple.h"
+#include "absl/strings/string_view.h"
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+/**
+ * An enumeration describing the result of a three-way comparison among
+ * strongly-ordered values (i.e. where comparison between values always yields
+ * less-than, equal-to, or greater-than).
+ *
+ * This is equivalent to:
+ *
+ *   * NSComparisonResult from the iOS/macOS Foundation framework.
+ *   * std::strong_ordering from C++20
+ *
+ * The values of the constants are specifically chosen so as to make casting
+ * between this type and NSComparisonResult possible.
+ */
+enum class ComparisonResult {
+  /** The left hand side was less than the right. */
+  Ascending = -1,
+
+  /** The left hand side was equal to the right. */
+  Same = 0,
+
+  /** The left hand side was greater than the right. */
+  Descending = 1
+};
+
+/**
+ * Returns the reverse order (i.e. Ascending => Descending) etc.
+ */
+constexpr ComparisonResult ReverseOrder(ComparisonResult result) {
+  return static_cast<ComparisonResult>(-static_cast<int>(result));
+}
+
+/**
+ * A generalized comparator for types in Firestore, with ordering defined
+ * according to Firestore's semantics. This is useful as argument to e.g.
+ * std::sort.
+ *
+ * Comparators are only defined for the limited set of types for which
+ * Firestore defines an ordering.
+ */
+template <typename T>
+struct Comparator {
+  // By default comparison is not defined
+};
+
+/** Compares two strings. */
+template <>
+struct Comparator<absl::string_view> {
+  bool operator()(const absl::string_view& left,
+                  const absl::string_view& right) const;
+};
+
+/** Compares two bools: false < true. */
+template <>
+struct Comparator<bool> : public std::less<bool> {};
+
+/** Compares two int32_t. */
+template <>
+struct Comparator<int32_t> : public std::less<int32_t> {};
+
+/** Compares two int64_t. */
+template <>
+struct Comparator<int64_t> : public std::less<int64_t> {};
+
+/** Compares two doubles (using Firestore semantics for NaN). */
+template <>
+struct Comparator<double> {
+  bool operator()(double left, double right) const;
+};
+
+/** Compare two byte sequences. */
+// TODO(wilhuff): perhaps absl::Span<uint8_t> would be better?
+template <>
+struct Comparator<std::vector<uint8_t>>
+    : public std::less<std::vector<uint8_t>> {};
+
+/**
+ * Perform a three-way comparison between the left and right values using
+ * the appropriate Comparator for the values based on their type.
+ */
+template <typename T>
+ComparisonResult Compare(const T& left, const T& right) {
+  Comparator<T> less_than;
+  if (less_than(left, right)) {
+    return ComparisonResult::Ascending;
+  } else if (less_than(right, left)) {
+    return ComparisonResult::Descending;
+  } else {
+    return ComparisonResult::Same;
+  }
+}
+
+#if __OBJC__
+/**
+ * Returns true if the given ComparisonResult and NSComparisonResult have the
+ * same integer values (at compile time).
+ */
+constexpr bool EqualValue(ComparisonResult lhs, NSComparisonResult rhs) {
+  return static_cast<int>(lhs) == static_cast<int>(rhs);
+}
+
+/**
+ * Performs a three-way comparison, identically to Compare, but converts the
+ * result to an NSComparisonResult.
+ *
+ * This function exists for interoperation with Objective-C++ and should
+ * eventually be removed.
+ */
+template <typename T>
+inline NSComparisonResult WrapCompare(const T& left, const T& right) {
+  static_assert(EqualValue(ComparisonResult::Ascending, NSOrderedAscending),
+                "Ascending invalid");
+  static_assert(EqualValue(ComparisonResult::Same, NSOrderedSame),
+                "Same invalid");
+  static_assert(EqualValue(ComparisonResult::Descending, NSOrderedDescending),
+                "Descending invalid");
+
+  return static_cast<NSComparisonResult>(Compare<T>(left, right));
+}
+#endif
+
+/** Compares a double and an int64_t. */
+ComparisonResult CompareMixedNumber(double doubleValue, int64_t longValue);
+
+/** Normalizes a double and then return the raw bits as a uint64_t. */
+uint64_t DoubleBits(double d);
+
+/**
+ * Compares the bitwise representation of two doubles, but normalizes NaN
+ * values. This is similar to what the backend and android clients do, including
+ * comparing -0.0 as not equal to 0.0.
+ */
+bool DoubleBitwiseEquals(double left, double right);
+
+/**
+ * Computes a bitwise hash of a double, but normalizes NaN values, suitable for
+ * use when using FSTDoublesAreBitwiseEqual for equality.
+ */
+size_t DoubleBitwiseHash(double d);
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_COMPARISON_H_
diff --git a/Firestore/core/src/firebase/firestore/util/string_apple.h b/Firestore/core/src/firebase/firestore/util/string_apple.h
index e1be8c3..108ade7 100644
--- a/Firestore/core/src/firebase/firestore/util/string_apple.h
+++ b/Firestore/core/src/firebase/firestore/util/string_apple.h
@@ -17,8 +17,13 @@
 #ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_APPLE_H_
 #define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_APPLE_H_
 
+// Everything in this header exists for compatibility with Objective-C.
+#if __OBJC__
+
 #import <Foundation/Foundation.h>
 
+#include "absl/strings/string_view.h"
+
 namespace firebase {
 namespace firestore {
 namespace util {
@@ -32,8 +37,16 @@ inline NSString* WrapNSStringNoCopy(const char* c_str) {
              freeWhenDone:NO];
 }
 
+// Creates an absl::string_view wrapper for the contents of the given NSString.
+inline absl::string_view MakeStringView(NSString* str) {
+  return absl::string_view(
+      [str UTF8String], [str lengthOfBytesUsingEncoding:NSUTF8StringEncoding]);
+}
+
 }  // namespace util
 }  // namespace firestore
 }  // namespace firebase
 
+#endif  // __OBJC__
+
 #endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_STRING_APPLE_H_